最大獨立集合的二分圖

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）

均爲三元素最大（如在，不能擴展）獨立集合，因此不是最大值（如最大可能）。