二部图中最小顶点覆盖算法

Question

我正在尝试找出一种算法来寻找二分图的最小顶点覆盖。

我在考虑一个解决方案，将问题简化为二部图中的最大匹配。众所周知，可以使用 bip 创建的网络中的最大流量找到它。图。

最大匹配M应该确定最小值。顶点覆盖 C，但我无法处理选择顶点来设置 C。 比方说bip。图有 X、Y 部分，最大匹配边的端点在集合 A 中，不属于 B 的顶点。

我会说我应该选择一个顶点作为 M 到 C 中的一条边。 特别是 M 中边 e 的端点连接到集合 B 中的顶点，否则如果它仅连接到 A 中的顶点则无关紧要。 不幸的是，这个想法通常行不通，因为可以找到我的算法的反例，因为 A 中的顶点也可以通过 M 中包含的边之外的其他边连接。

如有任何帮助，我们将不胜感激。

Answer 1

Kőnig's theorem证明正是这样做的——从二部图中的最大匹配构建最小顶点覆盖。

假设您有一个 G = (V, E) 二分图，在 X 和 Y 之间分隔。

正如您所说，首先您必须找到一个最大匹配(例如可以使用 Dinic's algorithm 来实现)。我们将此最大匹配称为 M。

然后构造你的最小顶点覆盖:

• 找到 U X¹ 中不匹配顶点的集合(可能为空)，即。未连接到 M
中的任何边
• 构建 Z 集合或顶点在 U 中，或通过交替路径连接到 U(在 的边之间交替的路径>M 和边不在 M)
• 那么 K = (X\Z) U (Y ∩ Z) 就是你的最小顶点覆盖

维基百科文章详细介绍了如何证明 K 确实是最小顶点覆盖。

---

¹ 或者Y，都是对称的