3

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

我正在考虑一个解决方案，将问题减少到二分图中的最大匹配。众所周知，可以使用从 bip 创建的网络中的最大流量来找到它。图形。

最大匹配 M 应确定最小值。顶点覆盖C，但我无法应付选择顶点来设置C。让我们说bip。图有 X、Y 部分，作为最大匹配边的端点的顶点在集合 A 中，不属于 B 的那些。

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

任何帮助都将不胜感激。

4

1 回答 1

0

Kőnig 的定理证明正是这样做的 - 从二分图中的最大匹配构建最小顶点覆盖。

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

正如你所说，首先你必须找到一个最大匹配（例如可以用Dinic 的算法来实现）。我们称之为M最大匹配。

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

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

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

1或 Y，两者都是对称的

于 2018-10-15T15:13:49.373 回答