Kőnig 定理 学习笔记

· · 算法·理论

Kőnig 定理及其证明

内容

Kőnig 定理：在任何二分图中，最大匹配的大小等于最小点覆盖的大小 ^{[1]}，即

\nu(G) = \tau(G)

证明

引理：对于任意图，若 M 是一个匹配，K 是一个点覆盖，满足

|M|=|K|

则 M 是最大匹配，K 是最小点覆盖。

证明：设 M^* 表示最大匹配，\tilde{K} 是最小点覆盖，那么

|M|\le|M^*|\le|\tilde{K}|\le|K|

由于 |M|=|K|，则 M=M^*，K=\tilde{K}。

定理证明：设图 G(X,Y,E) 为一个二分图，M^* 为 G 的最大匹配。令 U 表示 X 中所有未被匹配的点，Z 表示走 M^* 交错路径 ^{[2]} 过程中经过的所有点的集合。\ 令 S=Z \cap X，T=Z \cap Y，那么 T 中的所有顶点都被 M^* 匹配，且 N(S)=T（见下图）。

定义 K=(X\setminus S)\cup T，由于 G 的每一个边都必须至少有一个端点位于 K 中，否则就会存在一条边，其一端在 S 中，另一端在 Y\setminus T 中，这与 N(S) = T 矛盾。\ 因为 K 的大小为 X 集合中被匹配的顶点并上 Y 集合中为被匹配的顶点，就为 |M^*|，所以有

|M^*|=|K|

由引理得 |M^*|=|\tilde{K}| 成立。

注释

[1] : 匹配是边集的一个子集 ，满足其中任意两条边没有公共顶点。最大匹配即包含边数最多的匹配，大小记作 \nu(G)。\ 点覆盖是顶点集的一个子集 H \subseteq V，使得每条边至少有一个端点在 H 中。最小点覆盖即顶点数最少的点覆盖，大小记作 \tau(G)。

[2] : 一条 M 交错路是指这样一条路径，其中的每一条边交替地属于或不属于匹配 M。

参考文献