1

我正在尝试找到无向图的最大集，这是我用来这样做的算法：

1) 选择边数最少的节点 2) 消除它的所有邻居 3) 从其余节点中，选择边数最少的节点 4) 重复这些步骤，直到覆盖整个图

有人能告诉我这是否正确吗？如果不是，那么为什么这种方法在计算图中的最大独立集时是错误的？

4

3 回答 3

2

您所描述的将选择一个最大的独立集。我们可以看到如下：

  1. 这产生了一个独立的集合。通过矛盾，假设它没有。然后必须有两个由边连接的节点，这些节点被添加到您生成的集合中。先取其中一个（称它为 u，另一个为 v）然后当它被添加到集合中时，您将从集合中删除其所有相邻节点，包括节点 v。然后 v 不会已被添加到集合中，从而产生矛盾。

  2. 这产生了一个最大的独立集。通过矛盾，假设它没有。这意味着有一些节点 v 可以添加到您的算法生成的独立集合中，但没有添加。由于未添加此节点，因此它必须已通过算法从图中删除。这意味着它必须与已添加到集合中的某个节点相邻。但这是不可能的，因为这意味着如果不使结果不是独立集，就不能将节点 v 添加到生成的独立集。我们有矛盾。

希望这可以帮助！

于 2013-02-08T01:53:46.540 回答
0

任何图中都没有一个确定的最大独立集；以3个节点的循环为例，每个节点形成一个最大独立集。您的算法将为您提供图形的最大独立集之一，但不保证它具有最大基数。

另一方面，在图中找到最大独立集是 NP 完全的（因为该问题与找到最大团的问题是互补的），因此可能没有有效的算法。

于 2013-02-08T01:51:24.307 回答
0

在您在评论中澄清情况后，您的解决方案是正确的。更好的是，根据本文http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf的推论 3， 您可以获得子集顺序的良好近似值。 Greedy gives a 1 / (d + 1) -approximation for (unweighted) MIS in graphs of degree at most d

于 2013-02-08T02:00:53.283 回答