algorithm - 完整图分量数

Question

给定一个无向图。我如何检查它是否可以分为两组，其中一组中的每个节点都连接到它自己组中的每个其他节点(完整图)。一组可以为空或只有一个节点。不应保留任何节点。谢谢。

编辑:不禁止两组之间的边缘。

基本上我们必须检查图形是否可以分成两个团

Answer 1

正如@Damien 评论的那样，检查给定图的顶点是否可以划分为两个团实际上是clique cover 的决策问题。 k = 2。对于一般 k(即使 k = 3)，团覆盖问题已知是 NP 完全问题。对于 k = 2，存在一个 O(n²) 算法，基于下面的观察。

Given a graph G = (V, E), denote its complement as G'. Then V can be partitioned into two cliques if and only if G' is 2-colorable.

证明简单，此处省略。该算法的示意图如下所示。

01. construct G' from G;
02. if G' is bipartite
03.   return true;
04. else
05.   return false;

请注意，第一行需要 O(n²) 时间，而使用 BFS 测试 G' 是否二分仅需要 O(n + m) 时间，其中 n 是顶点数， m 是边数。因此，总复杂度为 O(n²)。