网络流之 - 匹配、边覆盖、独立集、顶点覆盖_匹配与边覆盖的关系

转载自：https://blog.sengxian.com/algorithms/networkflow-variants

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

概念

• 匹配 : 在$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}|=|V|$$
用文字描述就是:「最大匹配数 + 最小边覆盖数 = 顶点数」

证明

设最大匹配为 $M_{max}$，最小边覆盖为 $F_{min}$。
根据定义，最大匹配 $M$ 中所有的边共覆盖了 $2\times |M_{max}|$个顶点。
既然已经覆盖了 $2\times |M_{max}|$ 个顶点。
那么还有 $|V|-2\times |M_{max}|$个顶点未被覆盖。
我们在最大匹配的基础上加边，每加一条边最多可以扩展 $1$ 个顶点（如果能扩展 $2$ 个说明不是最大匹配），则最少要加$|V|-2\times |M_{max}|$条边。
所以$|F_{min}|=|V|-2\times |M_{max}|+|M_{max}|=|V|-|M_{max}|$。
得到$|M_{max}|+|F_{min}|=|V|$
证毕。
最大独立集与最小顶点覆盖
对于任意图（无所谓联通）而言
$$|S_{max}|+|S_{min}|=|V|$$
用文字描述就是「最大独立集数 + 最小顶点覆盖数 = 顶点数」。与之前的不同，这里的集合都是针对顶点的集合。

证明

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

求解

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

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