增广路定理 Berge's lemma¶
这是最大匹配的一个重要理论。
- 交错路（alternating path) 始于非匹配点且由匹配边与非匹配边交错而成。
- 增广路（augmenting path）是始于非匹配点且终于非匹配点的交错路。
增广路上非匹配边比匹配边数量多一，如果将匹配边改为未匹配边，反之亦然，则匹配大小会增加一且依然是交错路。
如图 匹配数从 2 增加为 3，我们称此过程为 增广。
根据 Berge's lemma 当找不到增广路的时候，得到最大匹配。
由此定理可知我们求最大匹配的核心思路。
核心思路
枚举所有未匹配点，找增广路径，直到找不到增广路径。
事实上，对于每个点只要枚举一次就好，证明如下：
假设某一轮沿着增广路 增广后，新增了以未匹配点 为起点的增广路 ，则 必与 有公共边（否则 不可能是因此次增广而新增的）。 在 与 取得公共边时，由于 是交错路，意味着相交点在 内的两邻边是不同类型的（图中以红和蓝表示）；因而增广前 就能走到 中的某个未匹配点，说明此前已存在从 出发的增广路，即已枚举过的未匹配点不再可能作为增广路起点。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：accelsao, Chrogeek, t4rf9
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用