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

Why is greedy algorithm not finding maximum independent set of a graph?

Answer 1

与 the original question answer 中的方法相同这里也适用，稍微修改一下图表:

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

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

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

两者都是三元素最大(例如，不能扩展)独立集，因此不是最大(例如，最大可能)。