知识卡片
两匹配对称差分解为路与环
两个匹配的对称差中,每个顶点度数至多2,因此连通分量只能是孤点、交替路径或偶长交替环。
若第二匹配更大,至少存在边数差条顶点不相交的第一匹配增广路。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第25章 二分图匹配 · 查看原书依据
Lemma 25.3 Let M and M* be matchings in graph G = (V, E), and consider the graph G′ = (V, E′), where E′ = M ⊕ M*. Then, G′ is a disjoint union of simple paths, simple cycles, and/or isolated vertices. The
参考来源
- 位置:《算法导论(第4版)》第25章《二分图匹配》(OEBPS/chapter025.xhtml,文本字符[5000,10000))。
- 结论依据:引理25.3由每点至多两条差异边证明分解,并推出增广路数量下界。
- 原始内容:Lemma 25.3 Let M and M * be matchings in graph G = ( V , E ), and consider the graph G ′ = ( V , E ′), where E ′ = M ⊕ M *. Then, G ′ is a disjoint union of simple paths, simple cycles, and/or isolated vertices. The