Sengxian's Blog

在图论中，有以下几个概念，它们之间的关系往往容易弄混淆，这里稍稍证明一下。
先放出概念 - 来自日本人的书。

概念

• 匹配 : 在 $G$ 中两两没有公共端点的边集合 $M \subseteq E$
• 边覆盖：在 $G$ 中的任意顶点都至少是 $F$ 中某条边的端点的 边集合 $F \subseteq E$ （边覆盖所有点）
• 独立集：在 $G$ 中两两互不相连的顶点集合 $S \subseteq V$
• 顶点覆盖：在 $G$ 中的任意边都有至少一个端点属于 $S$ 的顶点集合 $S \subseteq V$ （顶点覆盖所有边）

与之对应的，有最大匹配 $M_{max}$，最小边覆盖 $F_{min}$，最大独立集 $S_{max}$、最小顶点覆盖 $S_{min}$ 的概念，不过这个应该很好理解。

关系

它们之间是满足一些关系的。（废话

最大匹配与最小边覆盖

对于任意无孤立点的图而言

用中文描述就是「最大匹配数 + 最小边覆盖数 = 顶点数」

证明

设最大匹配为 $M_{max}$，最小边覆盖为 $F_{min}$。
根据定义，最大匹配 $M$ 中所有的边共覆盖了 $2 \times \vert M_{max} \vert$ 个顶点。
既然已经覆盖了 $2 \times \vert M_{max} \vert$ 个顶点。
那么还有 $\vert V \vert - 2 \times \vert M_{max} \vert$ 个顶点未被覆盖。
我们在最大匹配的基础上加边，每加一条边最多可以扩展 $1$ 个顶点（如果能扩展 $2$ 个说明不是最大匹配），则最少要加 $\vert V \vert - 2 \times \vert M_{max} \vert$ 条边。
所以 $\vert F_{min} \vert = \vert V \vert - 2 \times \vert M_{max} \vert + \vert M_{max} \vert = \vert V \vert - \vert M_{max} \vert$。
得到 $\vert M_{max} \vert + \vert F_{min} \vert = \vert V \vert$
证毕。

最大独立集与最小顶点覆盖

对于任意图（无所谓联通）而言

用中文描述就是「最大独立集数 + 最小顶点覆盖数 = 顶点数」。与之前的不同，这里的集合都是针对顶点的集合。

证明

设任意独立集 $S$。
则其补集 $\complement_{V}S$ 必定与 $S$ 中所有点之间有边联通（$S$ 中孤立点除外，但孤立点无边与之连接，不影响）。
根据独立集定义，任何 $S$ 中顶点没有边联通，所以任意边的端点一定有一个属于 $\complement_{V}S$。
所以 $\complement_{V}S$ 是一个顶点覆盖。
这就证明了 $S$ 为 $G$ 的独立集 -> $\complement_{V}S$ 为 $G$ 的顶点覆盖。
根据补集的定义，有 $\vert S \vert + \vert \complement_{V}S \vert = \vert V \vert$。
变形得到 $\vert \complement_{V}S \vert = \vert V \vert - \vert S \vert$
所以当且仅当 $S$ 为最大独立集时，$\complement_{V}S$ 为最小顶点覆盖。
即 $\vert S_{max} \vert + \vert S_{min} \vert = \vert V \vert$
证毕。

求解

借助这些关系，对于有最大匹配与最小边覆盖，最大独立集与最小顶点覆盖，求解出一个就可以求解出另一个。
对于最大匹配问题，二分图可以转化为网络流，一般图则一般用开花树（Edmonds）算法解决。
而对于最大独立集和最小顶点覆盖，却无法高效求解，他们是NP困难的。不过，对于二分图而言：

中文描述就是「最大匹配数 = 最小顶点覆盖数」。

这也被称为是二分图匹配的 König 定理。关于证明，请移步 http://www.matrix67.com/blog/archives/116。