为什么贪心算法没有找到二部图的最大独立集?
我试图使用贪婪方法解决二部图上的最大独立集问题。因此,碰到了这个帖子,它正是我想要做的。但是我只专注于二部图。答案中的反例不是二部图。
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
Why is greedy algorithm not finding maximum independent set of a graph?
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).