匹配相关证明

定义，在 $G(V,E)$ 中：

• $\alpha(G)$：最大点独立集的大小
• $\alpha'(G)$：最大匹配的大小或最大边独立集的大小
• $\beta(G)$：最小点覆盖的大小
• $\beta'(G)$：最小边覆盖的大小
• $n(G)$：$G$ 的点数
• $N_G(S),N(S)$：$S$ 的邻域，即所有与 $S$ 中至少一点有边相连的顶点集合

定理1：$\alpha(G)+\beta(G)=n(G)$

证明：在 $G$ 中，若 $S$ 是一个点独立集，则 $S$ 中没有边相连，那么所有边都至少有一个端点在 $\bar S$ 中，因此 $\bar S$ 是一个点覆盖，反之亦然。

所以 $\alpha(G)+\beta(G)=n(G)$。$\blacksquare$

定理2：若 $G$ 中没有孤立点，$\alpha'(G)+\beta'(G)=n(G)$。

证明：考虑构造证明两个不等式 $\alpha'(G)+\beta'(G)\le n(G)$ 和 $\alpha'(G)+\beta'(G)\ge n(G)$，联立即可得证。

令 $M$ 是 $G$ 的最大匹配，对于每个非饱和点，其不可能是孤立点，也不可能有边连向未饱和的点（否则这条边可以加入匹配），所以一定存在连向饱和点的边，考虑将其中一条加入 $M$。现在 $M$ 是一个边覆盖，除了 $M$ 中原有的匹配边使两个点饱和外，新加入的点都只使一个点饱和，所以总边数是 $n(G)-\alpha'(G)$，显然有 $n(G)-\alpha'(G)\ge\beta'(G)$，整理得 $\alpha'(G)+\beta'(G)\le n(G)$。

令 $L$ 是 $G$ 的最小边覆盖，对于 $L$ 中的每条边，其两个端点中至少有一个只被覆盖了一次（否则这条边可以删去，$L$ 仍是边覆盖），所以由 $L$ 中边构成的子图应该是若干个菊花。对于每个菊花，我们只保留一条边，就构造了一个匹配。假设某一菊花边数是 $k$，则点数是 $k+1$，所以 $n(G)-\beta'(G)$ 就是菊花的个数，因此我们的匹配大小也是 $n(G)-\beta'(G)$，显然有 $n(G)-\beta'(G)\le\alpha'(G)$，整理得 $\alpha'(G)+\beta'(G)\ge n(G)$。

联立，得证。$\blacksquare$

定理3（Konig 定理）：若 $G$ 是二分图，$\alpha'(G)=\beta(G)$。

证明：对于一个匹配，每条匹配边都至少需要一个点来覆盖它，所以有 $\alpha'(G)\le\beta(G)$。

令 $M$ 是 $G$ 的最大匹配，$X,Y$ 是 $G$ 作为二分图的两个部分，从 $X$ 中的所有非饱和点出发，走出一条交替路径，即按照一条非匹配边、一条匹配边的顺序，不难发现路径中的点除起点外一定都是饱和点，否则我们能够找到一条增广路。考虑将所有 $X$ 中不可到达的点和 $Y$ 中可以到达的点染黑，其余点染白，接下来证明所有黑点构成了一个大小为 $|M|$ 的点覆盖。

所有黑点都是饱和点，因为 $Y$ 中的黑点都是路径上的点且不是起点，所以饱和，而 $X$ 中所有非饱和点都会作为起点出现在路径中，由于黑点不会出现在路径中，所以饱和。同时不会有一条匹配边两端都是黑点，否则我们能够从 $Y$ 中的黑点走到 $X$ 中的黑点，矛盾。不会有一条边两端都是白点，否则，若这条边是匹配边，则我们从 $Y$ 通过另一条匹配边到达了 $X$，这意味着两条匹配边共端点，矛盾，若这条边不是匹配边，则我们能够通过 $X$ 中的白点走到 $Y$ 中的白点，矛盾。

整理发现，任意一条边的两端都至少有一点是黑色，同时匹配边两端恰有一个黑点，故所有黑点构成了一个大小为 $|M|$ 的点覆盖，得证。$\blacksquare$

推论：若 $G$ 是二分图，$\alpha(G)=\beta'(G)$。

证明：定理 1、2、3 联立即可。$\blacksquare$

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。