[科普中国]-最大完备子图

令U 为无向图G 的顶点的子集，当且仅当对于U 中的任意点u 和v ，(u , v) 是图G 的一条边时，U 定义了一个完全子图（complete subgraph ）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G 的一个更大的完全子图中时，它是图G 的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。

简介令U为无向图G的顶点的子集，当且仅当对于U中的任意点u和v，(u , v)是图G的一条边时，U定义了一个完全子图（complete subgraph）。子图的尺寸为图中顶点的数量。当且仅当一个完全子图不被包含在G的一个更大的完全子图中时，它是图G的一个完备子图。最大的完备子图是具有最大尺寸的完备子图。1

最大完备子图问题如果U定义了G的一个完全子图，则它也定义了的一个空子图，反之亦然。所以在G的完备子图与的独立集之间有对应关系。特别的，G的一个最大完备子图定义了的一个最大独立集。

最大完备子图问题是指寻找图G的一个最大完备子图。类似地，最大独立集问题是指寻找图G的一个最大独立集。这两个问题都是N P-复杂问题。当用算法解决其中一个问题时，也就解决了另一个问题。例如，如果有一个求解最大完备子图问题的算法，则也能解决最大独立集问题，方法是首先计算所给图的补图，然后寻找补图的最大完备子图。1

算法思想定义一个图，图中每个顶点表示一个网组。当且仅当两个顶点对应的网组交叉时，它们之间有一条边。所以该图的一个最大独立集对应于非交叉网组的一个最大尺寸的子集。当网组有一个端点在路径顶端，而另一个在底端时，非交叉网组的最大尺寸的子集能在多项式时间（实际上是(n2)）内用动态规划算法得到。当一个网组的端点可能在平面中的任意地方时，不可能有在多项式时间内找到非交叉网组的最大尺寸子集的算法。

最大完备子图问题和最大独立集问题可由回溯算法在O (n2n)时间内解决。两个问题都可使

用子集解空间树。考察最大完备子图问题。当试图移动到空间树的i层节点Z的左孩子时，需要证明从顶点i到每一个其他的顶点j（xj= 1且j在从根到Z的路径上）有一条边。当试图移动到Z的右孩子时，需要证明还有足够多的顶点未被搜索，以便在右子树有可能找到一个较大的完备子图。1

C++算法示例回溯算法可作为类AdjacencyGraph的一个成员来实现，为此首先要在该类中加入私有静态成员x（整型数组，用于存储到当前节点的路径），b e s t x（整型数组，保存目前的最优解），b e s t n（b e s t x中点的数量），c n（x中点的数量）。所以类AdjacencyGraph的所有实例都能共享这些变量。

函数maxClique是类AdjacencyGraph的一个私有成员，而MaxClique是一个共享成员。函数maxClique对解空间树进行搜索，而MaxClique初始化必要的变量。MaxClique( v )的执行返回最大完备子图的尺寸，同时它也设置整型数组v，当且仅当顶点i不是所找到的最大完备子图的一个成员时，v [ i ] = 0。1

最大完备子图

void AdjacencyGraph::maxClique(int i){// 计算最大完备子图的回溯代码 if (i > n) {// 在叶子上// 找到一个更大的完备子图，更新 for (int j = 1; j