最大独立集合的二分图

Question

我试图用贪婪的方法解决二分图上的最大独立集问题。所以遇到这个职位，这正是我想要做的。但我只专注于二部图。答案中的反案例不是双方图。有没有任何二分图，这一个不会工作？

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?

Answer 1

同样的方法在the original question answer在这里也适用，用稍微修改图：

开始通过删除＃5，剩下的就是一爪子图（节点（1,3,4,7））。以任何顺序移除它的叶子。您发现一个四节点独立集：（1,3,5,7）

从删除＃6开始。剩下的是4个周期。除去任何节点力或者这些组：

1. （1,3,6）
2. （2,4,6）

均为三元素最大（如在，不能扩展）独立集合，因此不是最大值（如最大可能）。