网络流之 - 匹配、边覆盖、独立集、顶点覆盖

以下摘抄：https://blog.sengxian.com/algorithms/networkflow-variants

Published on 2015-12-01

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

概念

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

与之对应的，有最大匹配$ M_{max}​$，最小边覆盖 F m i n ​ F_{min}​ Fmin​​，最大独立集 S m a x ​ S_{max}​ Smax​​、最小顶点覆盖 S m i n ​ S_{min}​ Smin​​ 的概念，不过这个应该很好理解。

关系

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

最大匹配与最小边覆盖

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

∣ M m a x ∣ + ∣ F m i n ∣ = ∣ V ∣ ​ \vert M_{max} \vert + \vert F_{min} \vert = \vert V \vert​ ∣Mmax​∣+∣Fmin​∣=∣V∣​

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

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

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

∣ S m a x ∣ + ∣ S m i n ∣ = ∣ V ∣ \vert S_{max} \vert + \vert S_{min} \vert = \vert V \vert ∣Smax​∣+∣Smin​∣=∣V∣

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

求解

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

∣ M m a x ∣ = ∣ S m i n ∣ \vert M_{max} \vert = \vert S_{min}\vert ∣Mmax​∣=∣Smin​∣

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