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

Question

给定图G,为什么跟随贪心算法不能保证找到最大的独立 G 集:

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

我不确定这是最简单的例子,但这是一个失败的:http://imgur.com/QK3DC

对于第一步,您可以选择B,C,D或F,因为它们都具有2阶段.假设我们删除B及其邻居.这使得F和D的度数为1,E为度数为2.在接下来的两个步骤中,我们删除F和D,最后设置为3,这是最大值.

相反,假设在第一步我们删除了C及其邻居.这给我们留下了F,A和E,每个都有一个度数为2.我们接下来其中一个,图表是空的,我们的解决方案只包含2个节点,正如我们所见,它不是最大的.