7

给定一个图 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

我想知道有人可以向我展示一个该算法失败的简单图表示例吗？

4

1 回答 1

9

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

第一步，您可以选择 B、C、D 或 F，因为它们的度数均为 2。假设我们删除 B 及其邻居。这使得 F 和 D 的度数为 1，E 的度数为 2。在接下来的两个步骤中，我们删除 F 和 D 并最终得到一个 3 的集合大小，这是最大值。

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

于 2012-12-17T20:55:29.820 回答