我试图找到一个无向图的最大集，这是我用来这样做的算法:
1) 选择边数最少的节点 2)消除它所有的邻居 3)从其余节点中，选择边数最少的节点 4)重复上述步骤，直到覆盖整个图
谁能告诉我这是否正确？如果不是，那么为什么这种方法计算图中的最大独立集是错误的？
最佳答案
您所描述的将选择一个最大独立集。我们可以看到如下:
这产生了一个独立的集合。自相矛盾，假设它没有。然后必须有两个节点通过添加到您生成的集合中的边连接。先选择其中一个(称它为 u，让另一个为 v)然后当它被添加到集合中时，您将从集合中删除它的所有相邻节点，包括节点 v。然后 v 不会已添加到集合中，给出矛盾。
这产生了一个最大独立集。自相矛盾，假设它没有。这意味着有一些节点 v 可以添加到您的算法生成的独立集中，但没有添加。由于未添加此节点，因此它一定已被算法从图中删除。这意味着它必须与已经添加到集合中的某个节点相邻。但这是不可能的，因为这将意味着节点 v 不能添加到产生的独立集而不使结果不是独立集。我们有矛盾。
希望这对您有所帮助!
关于algorithm - 计算最大独立集算法的正确性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14764374/