二分图的最大独立集 [英] Maximum independent sets of bipartite graph
问题描述
我试图解决在使用贪心方法二部图的最大独立集问题。因此，这个职位这不正是我试图做的来了。但我只在二部图集中。计数器情况下，在答案是没有一个二分图。是否有任何二部图，这其中不会工作？
I was trying to solve the maximum independent set problem on bipartite graphs using the greedy method. So came across this post which does exactly what i was trying to do. But am concentrating only on the bipartite graphs. The counter case in the answer is not a bipartite graph. Are there any bipartite graphs that this one wont work?
Greedy(G):
S = {}
While G is not empty:
Let v be a node with minimum degree in G
S = union(S, {v})
remove v and its neighbors from G
return S
<一个href="http://stackoverflow.com/questions/13921679/why-is-greedy-algorithm-not-finding-maximum-independent-set-of-a-graph">Why是贪婪算法没有找到最大独立集图的？
推荐答案
同样的方法在<一个href="http://stackoverflow.com/questions/13921679/why-is-greedy-algorithm-not-finding-maximum-independent-set-of-a-graph">the原来的问题的答案在这里也适用，用略作修改图：
The same approach as in the original question answer applies here as well, with a slightly modified graph:
通过删除＃5开始，剩下的就是一爪子图（节点（1,3,4,7））。以任意顺序取出它的叶子。你发现一个四节点独立设置：（1,3,5,7）
Start by removing #5, What's left is a paw graph (nodes (1,3,4,7)). Remove its leaves in any order. You discover a four-node independent set: (1,3,5,7)
通过删除＃6开始。剩下的就是一个4周期。删除任何节点力以下任一集：
Start by removing #6. What's left is a 4-cycle. Removing any node forces either of these sets:
- （1,3,6）
- （2,4,6）
都是三元素最大（如，不能扩大）独立集，并且因此不最大值（如在，最大可能的）。
both are three-element maximal (as in, cannot be expanded) independent sets, and thus not maximum (as in, the largest possible).
这篇关于二分图的最大独立集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
