7

除了在所有可能的独立集合中找到最大值的蛮力方法之外，我不相信存在一种算法可以在二分图中找到最大独立顶点集。

我想知道找到所有可能的顶点集的伪代码。

假设给定一个具有 4 个蓝色顶点和 4 个红色顶点的二分图。目前我会

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

我知道这种方式根本不会给我所有可能的独立集组合，因为在第一步之后，我选择了所有不匹配的下一个颜色顶点，而不是逐步完成所有可能。

例如给定一个匹配的图

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose red 2 and 4 since they dont match
  Add 2, 4 to independent Set
  Choose 2 and 3 from blue since they dont with 2 or 4 from red
  Add 2 and 3 from blue to independent set as well.
Independent Set = 1,2,3 from blue 2,4 from red
Repeat for blue 2, blue 3, ... red n (storing the cardinality for each set)

有没有办法改进这个算法以更好地搜索所有可能性。我知道|二部图的最大集| = |红色| + |蓝色| - |最大匹配|。

问题出现的可能性是，在第一次选择所有可能的红色以获得给定的蓝色时，如果这些红色连接到所有其他可能的蓝色，那么我的集合只有所有 1 个蓝色和其余红色。

4

2 回答 2

10

除了在所有可能的独立集合中找到最大值的蛮力方法之外，我不相信存在一种算法可以在二分图中找到最大独立顶点集。

有：找到最大独立集相当于找到最小顶点覆盖（通过对结果取补），并且Konig定理指出二分图中的最小顶点覆盖相当于最大匹配，并且可以在多项式中找到时间。我不知道找到所有匹配项，但似乎可以成倍增加。

于 2011-12-21T17:23:45.743 回答
1

正如 Aaron McDaid 在他现在已删除的答案中提到的那样，找到一个最大独立集的问题等同于找到一个最大集团。等价的是，在图 G 中找到一个最大独立集与在 G 的补集中找到一个最大团相同。这个问题已知是 NP 完全的。

你提到的蛮力解决方案需要O(n^2 2^n)，但你可以做得比这更好。Robson 在 1986 年发表了一篇题为“最大独立集的算法”的论文，该论文给出了一个采用O(2^{c*n})常数的算法0<c<1（我相信c大约是1/4，但我可能弄错了）。这些都不是二分图特有的。

如果你有一个二分图，需要注意的一点是任何一方都形成一个独立的集合。在完整的二部图K_{b,r}中，从每个顶点 in到每个顶点 inB x R和没有边，也没有在 内，最大独立集为if ，否则为。|B|=b|R|=rBRBRBb>=rR

服用B或R一般不会起作用。sdcvvc 用 vertices{1,2,3,A,B,C}和 edges记录了这个例子{A,1}, {A,2}, {A,3}, {B,3}, {C,3}。在这种情况下，最大独立集是{1,2,B,C}，它大于分区{A,B,C}或{1,2,3}。

它可能会改进 Robson 的算法，从较大的Bor开始，R然后从那里开始，尽管我不确定这会产生多大的不同。

或者，您可以对图的二部补码使用Hopcroft–Karp 算法来找到最大匹配，然后将匹配中使用的顶点作为独立集。这给出了一个多项式时间算法来解决这个问题。

于 2011-12-21T18:06:14.440 回答