为什么贪婪算法没有找到二分图的最大独立集？

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

为什么贪心算法没有找到最大的独立图集？

Answer 1

与原始问题答案中相同的方法也适用于此处,稍加修改的图表:

首先删除#5,剩下的是爪子图(节点(1,3,4,7)).以任何顺序移除它的叶子.您发现了一个四节点独立集:(1,3,5,7)

首先删除#6.剩下的是4个周期.删除任何节点会强制执行以下任一集合:

1. (1,3,6)
2. (2,4,6)

两者都是三元素最大(如在,不能扩展)独立集合,因此不是最大值(如在最大可能的情况下).