给定一个图 G，为什么下面的贪心算法不能保证找到 maximum independent set的 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
我想知道有人可以向我展示该算法失败的简单图表示例吗？
最佳答案
我不确定这是最简单的示例，但这是一个失败的示例:http://imgur.com/QK3DC
对于第一步，您可以选择 B、C、D 或 F，因为它们的度数都是 2。假设我们移除 B 及其邻居。这使得 F 和 D 的度数为 1，E 的度数为 2。在接下来的两个步骤中，我们删除 F 和 D，最终得到的集合大小为 3，这是最大值。
相反，假设我们在第一步中删除了 C 及其邻居。这给我们留下了 F、A 和 E，每个的度数大小为 2。接下来我们选择其中之一，图形为空，我们的解决方案仅包含 2 个节点，如我们所见，这不是最大值.
关于algorithm - 为什么贪心算法找不到图的最大独立集？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13921679/