Konig 定理 二分图最大匹配与最小点覆盖等

· · 个人记录

Konig 定理

在二分图中，最大匹配数等于最小点覆盖的点数。

说明

最小点覆盖，即选出一部分点使得每条边的两端点都至少被选出一个。求至少选出多少点。

构造证明

显然最大匹配数不超过最小点覆盖的点数（因为每一对匹配点都至少要选择一个）。

记 L, R 分别为左边的点集和右边的点集。

如果已知一个最大匹配，令 U 表示左边所有未匹配点，Z 表示从 U 出发走增广路（就是非匹配边和匹配边交替的路径）能到达的所有点。令 S = (L \setminus Z) \cup (R \cap Z)，即左边不能到达的点和右边能到达的点。

注意到从左边出发的增广路，相当于把非匹配边从左往右定向而匹配边从右往左定向形成的路径。于是对每条边 (u,v)

  1. 如果它是非匹配边，那么 u \in Z \implies v \in Z（因为 u 可以到达 v）；
  2. 如果它是匹配边，那么 u \in Z \iff v \in Z（因为 v 可以到达 u；并且只有 v 可以到 u，因为 u 只能连一个匹配边）。

可以发现无论 (u,v) 是不是匹配边，都不存在 u \in Z, v \notin Z 的情况。所以这样选出来的 S 是一个点覆盖。

接下来还需要说明 |S| = M。

由于我们从所有左边的未匹配点开始走，所以左边不能到达的点一定是匹配点。由于从左往右走不可能走到非匹配点（否则说明有一条两端都是非匹配点的增广路，这样就可以增广否则就有一条两端都是非匹配点的从左到右的增广路，与最大匹配矛盾)。所以右边能到达的点一定是匹配点。

综上，S 中所有点都是匹配点。但是由上面的 2. 可知，每条匹配边都恰好有一个点在 S 中。从而 |S| = M。

利用最小割最大流定理的证明

首先我们知道，二分图最大匹配可以转换成最大流问题。

转化为：建立源点 U 和汇点 V，从 U 到左边的点分别连一条流量为 1 的边；从右边的点到 V 分别连一条流量为 1 的边。中间的边我们设其流量为 +\infty。

然后我们知道，最大流问题和最小割问题对偶，它们的答案相同。

令最小割中 U 所处的连通分量点集为 Z，V 所处的连通分量点集为 Y。

由于我们割不掉 +\infty 的边，于是没有长成 (L \cap Z) \to (R \cap Y) 的边。这个最小割的容量即为 |L \cap Y| + |R \cap Z|。

我们直接令 S = (L \cap Y) \cup (R \cap Z)。由于没有 (L \cap Z) \to (R \cap Y) 的边，所以所有边都至少有一个端点在 S 中。由于最小割最大流定理，|S| = |L \cap Y| + |R \cap Z| = 最小割 = 最大流 = M。所以 S 是最小点覆盖。

最大独立集，最小边覆盖

最大独立集即为最小点覆盖的补集（显然，对于任意图都成立）。

二分图中最小边覆盖（如果存在，即没有度为 0 的点） = 总点数减去匹配数。

事实上这对任意图都成立：每条边都最多覆盖掉两个点；而那些覆盖掉两个点的边（一个点被重复覆盖不算）构成一个匹配。所以要最小化边覆盖，就等价于最大匹配。

构造办法即为选取所有匹配边，然后每个未匹配点随便选一条边。