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

问题描述

给定一个图G，为什么下面的贪心算法不能保证找到最大独立集的G

Given a graph G, why is following greedy algorithm not guaranteed to find maximum independent set of 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

我想知道，有人可以告诉我一个图，其中该算法失败？

I am wondering can someone show me a simple example of a graph where this algorithm fails?

推荐答案

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

I'm not sure this is the simplest example, but here is one that fails: http://imgur.com/QK3DC

有关的第一步，可以选择B，C，D或F，因为它们都具有程度2.假设我们删除B和它的邻国。这使得F和D与学位1和E度2。在接下来的两个步骤，我们会删除F和D，最终以3组大小，这是最大的。

For the first step, you can choose B, C, D, or F since they all have degree 2. Suppose we remove B and its neighbors. That leaves F and D with degree 1 and E with degree 2. During the next two steps, we remove F and D and end up with a set size of 3, which is the maximum.

相反，假设在我们删除C和其邻国的第一步。这给我们留下了F，A和E，各有2的程度大小，我们取其中一种的旁边，和图形是空的，我们的解决方案只包含2个节点，正如我们所看到的，是不是最大

Instead suppose on the first step we removed C and its neighbors. This leaves us with F, A and E, each with a degree size of 2. We take either one of these next, and the graph is empty and our solution only contains 2 nodes, which as we have seen, isn't the maximum.

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