知识卡片
匹配要求每个顶点至多占一边
图的匹配是边集合M,每个顶点至多与M中一条边相接。
最大匹配以边数|M|最大为目标,而非让某一条边权最大。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第24章 最大流 · 查看原书依据
a matching is a subset of edges M ⊆ E such that for all vertices v ∈ V, at most one edge of M is incident on v. We say that a vertex v ∈ V is matched by the matching M if some edge in M is incident on v, and
参考来源
- 位置:《算法导论(第4版)》第24章《最大流》(OEBPS/chapter024.xhtml,文本字符[40000,45000))。
- 结论依据:24.3节明确定义匹配和最大基数匹配。
- 原始内容:a matching is a subset of edges M ⊆ E such that for all vertices v ∈ V , at most one edge of M is incident on v . We say that a vertex v ∈ V is matched by the matching M if some edge in M is incident on v , and