增广路定理 Berge's lemma

这是最大匹配的一个重要理论。

  • 交错路(alternating path) 始于非匹配点且由匹配边与非匹配边交错而成。
  • 增广路(augmenting path)是始于非匹配点且终于非匹配点的交错路。

增广路上非匹配边比匹配边数量多一,如果将匹配边改为未匹配边,反之亦然,则匹配大小会增加一且依然是交错路。

augment-1

如图 匹配数从 2 增加为 3,我们称此过程为 增广

根据 Berge's lemma 当找不到增广路的时候,得到最大匹配。

由此定理可知我们求最大匹配的核心思路。

核心思路

枚举所有未匹配点,找增广路径,直到找不到增广路径。

事实上,对于每个点只要枚举一次就好,证明如下:

augment-2

假设某一轮沿着增广路 a - b 增广后,新增了以未匹配点 x 为起点的增广路 P_x,则 P_x 必与 a - b 有公共边(否则 P_x 不可能是因此次增广而新增的)。 在 P_xa - b 取得公共边时,由于 a - b 是交错路,意味着相交点在 a - b 内的两邻边是不同类型的(图中以红和蓝表示);因而增广前 x 就能走到 a - b 中的某个未匹配点,说明此前已存在从 x 出发的增广路,即已枚举过的未匹配点不再可能作为增广路起点。


评论