完整图形组件的数量 [英] Number of complete graph components

问题描述

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

Given an undirected graph. How do I check if it can be divided into two sets where every node of one set is connected to every other node of its own set (complete graph). A set can be empty or of only one node. No node should be remaining. Thanks.

两组之间的边缘不被禁止.

Edges between two sets is not forbidden.

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

推荐答案

如@Damien所述，检查给定图的顶点是否可以划分为两个集团实际上是

As commented by @Damien, checking whether vertices of a given graph can be partitioned into two cliques is actually the decision problem of clique cover with k = 2. For general k (even for k = 3), the clique cover problem is known to be NP-complete. For k = 2, there exists a O(n²) algorithm, based on the observation below.

给定一个图G =(V，E)，将其补码表示为G'.然后，且仅当G'是2色的时，V才能划分为两个类别.

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.

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

The proof is simple and thus omitted here. The sketch of the algorithm is shown below.

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是顶点数，而n是顶点数. m是边数.因此，总复杂度为O(n ² ).

Note that the first line requires O(n²) time, while testing whether G' is bipartite requires only O(n + m) time using BFS, where n is the # of vertices and m is the # of edges. Therefore, the total complexity is O(n²).

这篇关于完整图形组件的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！