【問題描述】

當 G′?是圖 G?的子圖，且 G′?是關于 V′ 的完全圖時，子圖 G' 為圖 G 的團；當 G' 是團，且不是其他團的子集時，G' 為圖 G 的極大團；當 G' 是極大團時，且點數最多，G' 為圖 G 最大團

當 G′ 中所有點不相鄰，最大點集最大的圖 G′ 為圖 G 的最大獨立集，且最大獨立集數=補圖的最大團

當用個數最少的團覆蓋圖 G 所有的點時，稱為最小團覆蓋，由于每個團中最多取一個點，因此有最大獨立集<=最小團覆蓋

簡單來說，極大團是增加任一頂點都不再符合定義的團，最大團是圖中含頂點數最多的極大團，最大獨立集是除去圖中的團后的點集，而最大團問題就是在一個無向圖中找出一個點數最多的完全圖。

對于弦圖來說，求最大團一般使用 MCS 算法，而對于一般圖來說，常使用 Bron-Kerbosch 算法

關于弦圖的最大團：點擊這里

【Bron-Kerbosch 算法】

Bron-Kerbosch 算法用于計算圖中的最大的全連通分量，即計算圖的最大團。

1.算法原理

Bron-Kerbosch 算法的基礎形式是一個遞歸回溯的搜索算法，其通過給定三個集合：R、P、X 來遞歸的進行搜索

初始化集合 R、X 分別為空，集合 P 為所有頂點的集合

每次從集合 P 中取頂點 {vi}，當集合中沒有頂點時，有兩種情況：
1）集合 R 是最大團，此時集合 X 為空
2）無最大團，此時回溯

對于每一個從集合 P 中取得的頂點 {vi}，有如下處理：
1）將頂點 {vi} 加到集合 R 中，集合 P、X 與頂點 {vi} 得鄰接頂點集合 N{vi} 相交，之后遞歸集合 R、P、X
2）從集合 P 中刪除頂點 {vi}，并將頂點 {vi} 添加到集合 X 中
3）若集合 P、X 都為空，則集合 R 即為最大團

總的來看，就是每次從集合 P 中取 vi 后，再從?P∩N{vi} 集合中取相鄰結點，保證集合 R 中任意頂點間都兩兩相鄰

偽代碼過程

BronKerbosch1(R,P,X):if P and X are both empty:report R as a maximal cliquefor each vertex v in P:BronKerbosch1(R ? {v}, P ? N(v), X ? N(v))P := P \ {v}X := X ? {v}

2.算法優化

對于基礎的算法，由于其遞歸搜索了所有情況，對其中有些不是最大團的也進行了搜索，效率不高，為了節省時間讓算法更快的回溯，可以通過設定關鍵點來進行搜索。

由于對于任意的最大團，其必須包括頂點 {u} 或 N-N{u}，不然其必然需要通過添加它們來進行擴充，這顯然矛盾，所以僅需測試頂點 {u} 以及 N-N{u} 即可。

偽代碼過程：

BronKerbosch2(R,P,X):if P and X are both empty:report R as a maximal cliquechoose a pivot vertex u in P ? Xfor each vertex v in P \ N(u):BronKerbosch2(R ? {v}, P ? N(v), X ? N(v))P := P \ {v}X := X ? {v}

由于其是通過選擇特殊點，來進行最小化遞歸調用，一定程度上節省了時間，但還可以與降序的方式結合使用，來保證在線性的時間內求子圖的最大團

偽代碼過程：

BronKerbosch3(G):P = V(G)R = X = emptyfor each vertex v in a degeneracy ordering of G:BronKerbosch2(R ? {v}, P ? N(v), X ? N(v))P := P \ {v}X := X ? {v}

3.實現

int n,m; bool G[N][N]; int cnt[N];//cnt[i]為>=i的最大團點數 int group[N];//最大團的點 int vis[N];//記錄點的位置 int res;//最大團的數目 bool dfs(int pos,int num){//num為當前獨立集中的點數for(int i=pos+1;i<=n;i++){if(cnt[i]+num<=res)//剪枝，若取i但cnt[i]+已經取了的點數仍<ansreturn false;if(G[pos][i]){//與當前團中元素比較，取Non-N(i)int j;for(j=0;j<num;j++)if(!G[i][vis[j]])break;if(j==num){//若為空，則皆與i相鄰，則此時將i加入到最大團中vis[num]=i;if(dfs(i,num+1))return true;}}}if(num>res){//每添加一個點最多使最大團數+1,后面的搜索就沒有意義了for(int i=0;i<num;i++)//最大團的元素group[i]=vis[i];res=num;//最大團中點的數目return true;}return false; } void maxClique(){res=-1;for(int i=n;i>0;i--){//枚舉所有點vis[0]=i;dfs(i,1);cnt[i]=res;} } int main(){int T;scanf("%d",&T);while(T--){memset(G,0,sizeof(G));scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);G[x][y]=1;G[y][x]=1;}//建立反圖for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j)G[i][j]=0;elseG[i][j]^=1;}}maxClique();if(res<0)res=0;printf("%d\n",res);//最大團的個數for(int i=0;i<res;i++)//最大團中的頂點printf("%d ",group[i]);printf("\n");}return 0; }

【例題】

Maximum Clique（HDU-1530）(模板題)：點擊這里

Graph Coloring（POJ-1419）(模板題)：點擊這里

總結

以上是生活随笔為你收集整理的图论 —— 最大团问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。