[科普中國]-最大完備子圖

令U 為無向圖G 的頂點的子集，當且僅當對于U 中的任意點u 和v ，(u , v) 是圖G 的一條邊時，U 定義了一個完全子圖（complete subgraph ）。子圖的尺寸為圖中頂點的數(shù)量。當且僅當一個完全子圖不被包含在G 的一個更大的完全子圖中時，它是圖G 的一個完備子圖。最大的完備子圖是具有最大尺寸的完備子圖。

簡介令U為無向圖G的頂點的子集，當且僅當對于U中的任意點u和v，(u , v)是圖G的一條邊時，U定義了一個完全子圖（complete subgraph）。子圖的尺寸為圖中頂點的數(shù)量。當且僅當一個完全子圖不被包含在G的一個更大的完全子圖中時，它是圖G的一個完備子圖。最大的完備子圖是具有最大尺寸的完備子圖。1

最大完備子圖問題如果U定義了G的一個完全子圖，則它也定義了的一個空子圖，反之亦然。所以在G的完備子圖與的獨立集之間有對應關系。特別的，G的一個最大完備子圖定義了的一個最大獨立集。

最大完備子圖問題是指尋找圖G的一個最大完備子圖。類似地，最大獨立集問題是指尋找圖G的一個最大獨立集。這兩個問題都是N P-復雜問題。當用算法解決其中一個問題時，也就解決了另一個問題。例如，如果有一個求解最大完備子圖問題的算法，則也能解決最大獨立集問題，方法是首先計算所給圖的補圖，然后尋找補圖的最大完備子圖。1

算法思想定義一個圖，圖中每個頂點表示一個網(wǎng)組。當且僅當兩個頂點對應的網(wǎng)組交叉時，它們之間有一條邊。所以該圖的一個最大獨立集對應于非交叉網(wǎng)組的一個最大尺寸的子集。當網(wǎng)組有一個端點在路徑頂端，而另一個在底端時，非交叉網(wǎng)組的最大尺寸的子集能在多項式時間（實際上是(n2)）內(nèi)用動態(tài)規(guī)劃算法得到。當一個網(wǎng)組的端點可能在平面中的任意地方時，不可能有在多項式時間內(nèi)找到非交叉網(wǎng)組的最大尺寸子集的算法。

最大完備子圖問題和最大獨立集問題可由回溯算法在O (n2n)時間內(nèi)解決。兩個問題都可使

用子集解空間樹?？疾熳畲笸陚渥訄D問題。當試圖移動到空間樹的i層節(jié)點Z的左孩子時，需要證明從頂點i到每一個其他的頂點j（xj= 1且j在從根到Z的路徑上）有一條邊。當試圖移動到Z的右孩子時，需要證明還有足夠多的頂點未被搜索，以便在右子樹有可能找到一個較大的完備子圖。1

C++算法示例回溯算法可作為類AdjacencyGraph的一個成員來實現(xiàn)，為此首先要在該類中加入私有靜態(tài)成員x（整型數(shù)組，用于存儲到當前節(jié)點的路徑），b e s t x（整型數(shù)組，保存目前的最優(yōu)解），b e s t n（b e s t x中點的數(shù)量），c n（x中點的數(shù)量）。所以類AdjacencyGraph的所有實例都能共享這些變量。

函數(shù)maxClique是類AdjacencyGraph的一個私有成員，而MaxClique是一個共享成員。函數(shù)maxClique對解空間樹進行搜索，而MaxClique初始化必要的變量。MaxClique( v )的執(zhí)行返回最大完備子圖的尺寸，同時它也設置整型數(shù)組v，當且僅當頂點i不是所找到的最大完備子圖的一個成員時，v [ i ] = 0。1

最大完備子圖

void AdjacencyGraph::maxClique(int i){// 計算最大完備子圖的回溯代碼 if (i > n) {// 在葉子上// 找到一個更大的完備子圖，更新 for (int j = 1; j