algorithm - 为什么贪心算法找不到二部图的最大独立集？

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)

两者都是三元素最大（如，不能扩展）独立集合，因此不是最大值（如，最大可能）。