algorithm - 图算法？

Question

如果我想确定一个图是否可以分为两个子图，其中每个子图中每个节点都连接到每个其他节点，那么最有效的方法是什么。例如，在图像中，图可以被分组分成两个子图，分别由 4 个节点和 5 个节点组成，在每个子图中，每个节点都连接到每个其他节点。假设给我一张图，我要检查上述事实是否成立，最有效的方法或算法是什么。

Answer 1

这被称为 clique problem . clique是顶点的一个子集，使得该子集中的每两个顶点在原始图中都是相连的(即它们形成一个完整的子图)。您要求的算法列出所有最大派系(不属于较大派系的派系)。为此有多种算法。通常使用的是 Bron-Kerbosch algorithm .它的最坏情况运行时间为 O(3^n/3)，其中 n 是图中的顶点数。

如果您的图形具有特殊结构(例如，平面，您的示例不是)，则其他算法可能适用。

编辑:实际上，如果您的决策问题是图形是否可以恰好划分为两个集团，则有一个更有效的算法，如 this thread 中所述。 (然后成为您问题的副本)。