2

我一直在尝试用下面提到的算法解决最大集团问题，但到目前为止还没有找到失败的情况。
算法：
对于给定的图，每个节点从 1 到 N 编号。
1. 将节点视为永久节点并形成一组节点，使得每个节点都连接到该永久节点。（该集合也包括永久节点）
2 . 现在形成原始图的子图，使其包含所形成的集合中的所有节点，并且仅包含在集合中存在的节点之间的那些边。
3. 求每个节点的度数。
4. 如果所有节点的度数相同，则我们有一个集团。
5. 否则从该子图中删除最小度数节点并从步骤 3 开始重复。
6. 对图中的所有节点重复步骤 1-5。

谁能指出这个算法的缺陷？
这是我的代码 http://pastebin.com/tN149P9m。

4

2 回答 2

6

这是一系列反例。从 k 集团开始。对于这个团中的每个节点，将其连接到 K_{k-1,k-1} 的新副本的每个节点，即 k-1 加上 k-1 个节点上的完整二分图。对于 clique 中的每个永久节点，残差图是其 K_{k-1,k-1} 和 clique 的副本。K_{k-1,k-1} 中的节点的度数为 k，其他 clique 节点的度数为 k-1，因此后者被删除。

这是一个 16 节点的反例，通过设置 k = 4 并识别环中的 K_{3,3} 部分获得：

{0: {1, 2, 3, 4, 5, 6, 7, 8, 9},
 1: {0, 2, 3, 7, 8, 9, 10, 11, 12},
 2: {0, 1, 3, 10, 11, 12, 13, 14, 15},
 3: {0, 1, 2, 4, 5, 6, 13, 14, 15},
 4: {0, 3, 7, 8, 9, 13, 14, 15},
 5: {0, 3, 7, 8, 9, 13, 14, 15},
 6: {0, 3, 7, 8, 9, 13, 14, 15},
 7: {0, 1, 4, 5, 6, 10, 11, 12},
 8: {0, 1, 4, 5, 6, 10, 11, 12},
 9: {0, 1, 4, 5, 6, 10, 11, 12},
 10: {1, 2, 7, 8, 9, 13, 14, 15},
 11: {1, 2, 7, 8, 9, 13, 14, 15},
 12: {1, 2, 7, 8, 9, 13, 14, 15},
 13: {2, 3, 4, 5, 6, 10, 11, 12},
 14: {2, 3, 4, 5, 6, 10, 11, 12},
 15: {2, 3, 4, 5, 6, 10, 11, 12}}
于 2014-03-25T18:05:30.527 回答
3

你提出的看起来很像下面的排序算法结合贪婪的集团搜索：

考虑一个简单的无向图 G=(V,E)

初始排序

选择度数最小的顶点并将其放在新列表 L 中的第一位。从剩余的顶点中选择度数最小的顶点并将其放置在 L 中的第二个位置。重复这些操作，直到 V 中的所有顶点都在 L 中。

贪婪地寻找派系

从 L 中的最后一个顶点开始并以相反的顺序移动。对于L 计算团中的每个顶点v ，如下所示：

  1. 将 v 添加到新的 clique C
  2. 计算 L 中 v 的邻居集：N(v)
  3. 选择N(v) 中的最后一个顶点
  4. v=w; L=L 与 N(v) 的交点；
  5. 重复步骤 1 到 4

实际上，建议的初始排序称为简并排序，并将 G 分解为 k 核（参见Batagelj 等人，2002 年）。 k 核是一个最大子图，其所有顶点至少具有k度。初始排序在最后留下最高的核心（具有最大的k）。当以相反的顺序选择顶点时，您首先在最高核心中选择顶点（类似于您的步骤 4）并尝试在那里找到派系。还有许多其他的可能性可以根据 k 核贪婪地找到派系，但除非您进行全面枚举，否则您永远无法保证最佳。

例如，在搜索精确的最大团时使用建议的初始排序，并且已在许多研究论文中进行了描述，例如[Carraghan 和 Pardalos 90]

于 2014-07-22T20:04:17.453 回答