完整图形组件的数量

Question

给出一个无向图.如何检查是否可以将其分为两组,其中一组中的每个节点都连接到其自身组的每个其他节点(完整图形).集合可以是空的,也可以只有一个节点.不应该留下任何节点.谢谢.

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

基本上我们必须检查图表是否可以分为两个派系

Answer 1

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

给定图G =(V,E),将其补码表示为G'.然后,当且仅当G'是2可着色时,V可以被分成两个团.

证明很简单,因此在此省略.算法草图如下所示.

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

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