最大独立集算法

我不相信存在于比寻找所有可能的独立集合中最大的蛮力方法以外的二分图中发现的最大独立顶点集的算法。最大独立集算法

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

说给出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)

有没有一种方法，我可以改善这种算法为所有可能更好的搜索。我知道|双极图|最大集| = | Red | + |蓝色| - |最大匹配|。

问题出现与通过选择在第一次去的所有可能的红色为一个给定的蓝色，如果这些红色连接到所有其他可能的蓝色，然后我一套永远只拥有全部为1米的蓝色和红色休息的可能性。

来源

2011-12-21 user1084113

图表有多大？节点数和边数？用标准的最大集团算法提供图形的补充可能是可能的。 – 2011-12-21 17:23:16

我不相信有一种算法找到最大的独立顶点集在二分图中，而不是在所有可能的独立集中找到最大值的蛮力方法。

有：找到最大独立集是等价于求的最小顶点覆盖（通过取结果的补码），和Konig's theorem指出，在二分图最小顶点覆盖相当于最大匹配，而且该可以在多项式时间中找到。我不知道如何找到所有的配对，但似乎可以指数多。

来源

2011-12-21 17:23:45 sdcvvc

我看不到顶点覆盖和独立集之间的连接。我认为顶点封面的补充不是一个独立的集合。 – 2011-12-21 17:26:56

顶点覆盖：对于所有边（u，v），无论是C中还是v中C.独立集：对于所有边（u，v），u不在I中或v不在I中。条件是如果你把我作为C的补充，就是等价的。 – sdcvvc 2011-12-21 17:28:31

关于[Konig's theorem]的文章（http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29）显示了一个矛盾的例子。在右上角，您可以看到两个红色节点之间的边缘。这展示了一个不是独立的（最小）顶点覆盖。 – 2011-12-21 17:29:07

亚伦McDaid提到他现在删除了答案，问题找到一个最大独立集就相当于找到最大团。等价的是，在图G中找到最大独立集与在G的补集中找到最大集相同。这个问题被称为NP完全。

你提到的蛮力解决方案采用O(n^2 2^n)，但你可以做得比这更好。 Robson有一篇题为“1986年最大独立集的算法”的文章，它给出了一个算法，该算法需要0<c<1（我相信c约为1/4，但我可能会误）。。

有一点要注意，如果你有一个二分图是两侧形成独立的组，在完成二分图K_{b,r}被分隔B x R与|B|=b和|R|=r那里是从每一个顶点B边缘的每一个顶点在R中且没有在B之内，也没有在R之内，最大独立集合为B if b>=r，否则为R。

以B或R一般不会工作。sdcvvc注意到顶点{1,2,3,A,B,C}和边缘{A,1}, {A,2}, {A,3}, {B,3}, {C,3}的例子。在这种情况下，最大独立集是{1,2,B,C}，它大于分区{A,B,C}或{1,2,3}。

它可能会改善Robson的算法，以B或R中的较大值开始，并从那里开始，但我不确定这会产生多大的差异。

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

来源

2011-12-21 18:06:14 PengOne

没有科尼格定理，我认为最后一段是正确的。例如，如果图形是完整的二部分，则其二部分补足为空，Hopcroft-Karp算法不会找到任何匹配，而最佳方法是取所有蓝色（或红色）顶点。 – sdcvvc 2011-12-21 21:54:47

PengOne，我删除了我的答案，因为一旦我理解了@ sdcvvc的回答，我决定人们应该而不是我的答案。据我所知，这是正确的。 – 2011-12-22 03:48:14

Robson算法是否有软件实现？ – simon 2015-12-18 11:50:14

最大独立集算法

回答

相关问题