为什么贪心算法没有找到二部图的最大独立集？ [英] Why is greedy algorithm not finding maximum independent set of a bipartite graph?

问题描述

我试图使用贪婪方法解决二部图上的最大独立集问题。因此，碰到了这个帖子，它正是我想要做的。但是我只专注于二部图。答案中的反例不是二部图。

I was trying to solve the maximum independent set problem on bipartite graphs using the greedy method. So came across this post which does exactly what i was trying to do. But am concentrating only on the bipartite graphs. The counter case in the answer is not a bipartite graph. Are there any bipartite graphs that this one wont work?

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?

推荐答案

与也适用于此处，但图形略有修改：

The same approach as in the original question answer applies here as well, with a slightly modified graph:

从删除＃5开始，剩下的是一个爪子图（节点（1,3,4,7））。以任何顺序取下其叶子。您发现一个四节点独立集：（1,3,5,7）

Start by removing #5, What's left is a paw graph (nodes (1,3,4,7)). Remove its leaves in any order. You discover a four-node independent set: (1,3,5,7)

首先删除＃6。剩下的是4个周期。删除任何节点都会强制使用以下任一集合：

Start by removing #6. What's left is a 4-cycle. Removing any node forces either of these sets:

1. （1,3,6）


2. （ 2,4,6）

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

both are three-element maximal (as in, cannot be expanded) independent sets, and thus not maximum (as in, the largest possible).

这篇关于为什么贪心算法没有找到二部图的最大独立集？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！