【問(wèn)題描述】

當(dāng) G′?是圖 G?的子圖，且 G′?是關(guān)于 V′ 的完全圖時(shí)，子圖 G' 為圖 G 的團(tuán)；當(dāng) G' 是團(tuán)，且不是其他團(tuán)的子集時(shí)，G' 為圖 G 的極大團(tuán)；當(dāng) G' 是極大團(tuán)時(shí)，且點(diǎn)數(shù)最多，G' 為圖 G 最大團(tuán)

當(dāng) G′ 中所有點(diǎn)不相鄰，最大點(diǎn)集最大的圖 G′ 為圖 G 的最大獨(dú)立集，且最大獨(dú)立集數(shù)=補(bǔ)圖的最大團(tuán)

當(dāng)用個(gè)數(shù)最少的團(tuán)覆蓋圖 G 所有的點(diǎn)時(shí)，稱(chēng)為最小團(tuán)覆蓋，由于每個(gè)團(tuán)中最多取一個(gè)點(diǎn)，因此有最大獨(dú)立集<=最小團(tuán)覆蓋

簡(jiǎn)單來(lái)說(shuō)，極大團(tuán)是增加任一頂點(diǎn)都不再符合定義的團(tuán)，最大團(tuán)是圖中含頂點(diǎn)數(shù)最多的極大團(tuán)，最大獨(dú)立集是除去圖中的團(tuán)后的點(diǎn)集，而最大團(tuán)問(wèn)題就是在一個(gè)無(wú)向圖中找出一個(gè)點(diǎn)數(shù)最多的完全圖。

對(duì)于弦圖來(lái)說(shuō)，求最大團(tuán)一般使用 MCS 算法，而對(duì)于一般圖來(lái)說(shuō)，常使用 Bron-Kerbosch 算法

關(guān)于弦圖的最大團(tuán)：點(diǎn)擊這里

【Bron-Kerbosch 算法】

Bron-Kerbosch 算法用于計(jì)算圖中的最大的全連通分量，即計(jì)算圖的最大團(tuán)。

1.算法原理

Bron-Kerbosch 算法的基礎(chǔ)形式是一個(gè)遞歸回溯的搜索算法，其通過(guò)給定三個(gè)集合：R、P、X 來(lái)遞歸的進(jìn)行搜索

初始化集合 R、X 分別為空，集合 P 為所有頂點(diǎn)的集合

每次從集合 P 中取頂點(diǎn) {vi}，當(dāng)集合中沒(méi)有頂點(diǎn)時(shí)，有兩種情況：
1）集合 R 是最大團(tuán)，此時(shí)集合 X 為空
2）無(wú)最大團(tuán)，此時(shí)回溯

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

總的來(lái)看，就是每次從集合 P 中取 vi 后，再?gòu)?P∩N{vi} 集合中取相鄰結(jié)點(diǎn)，保證集合 R 中任意頂點(diǎn)間都兩兩相鄰

偽代碼過(guò)程

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.算法優(yōu)化

對(duì)于基礎(chǔ)的算法，由于其遞歸搜索了所有情況，對(duì)其中有些不是最大團(tuán)的也進(jìn)行了搜索，效率不高，為了節(jié)省時(shí)間讓算法更快的回溯，可以通過(guò)設(shè)定關(guān)鍵點(diǎn)來(lái)進(jìn)行搜索。

由于對(duì)于任意的最大團(tuán)，其必須包括頂點(diǎn) {u} 或 N-N{u}，不然其必然需要通過(guò)添加它們來(lái)進(jìn)行擴(kuò)充，這顯然矛盾，所以?xún)H需測(cè)試頂點(diǎn) {u} 以及 N-N{u} 即可。

偽代碼過(guò)程：

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}

由于其是通過(guò)選擇特殊點(diǎn)，來(lái)進(jìn)行最小化遞歸調(diào)用，一定程度上節(jié)省了時(shí)間，但還可以與降序的方式結(jié)合使用，來(lái)保證在線性的時(shí)間內(nèi)求子圖的最大團(tuán)

偽代碼過(guò)程：

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.實(shí)現(xiàn)

int n,m; bool G[N][N]; int cnt[N];//cnt[i]為>=i的最大團(tuán)點(diǎn)數(shù) int group[N];//最大團(tuán)的點(diǎn) int vis[N];//記錄點(diǎn)的位置 int res;//最大團(tuán)的數(shù)目 bool dfs(int pos,int num){//num為當(dāng)前獨(dú)立集中的點(diǎn)數(shù)for(int i=pos+1;i<=n;i++){if(cnt[i]+num<=res)//剪枝，若取i但cnt[i]+已經(jīng)取了的點(diǎn)數(shù)仍<ansreturn false;if(G[pos][i]){//與當(dāng)前團(tuán)中元素比較，取Non-N(i)int j;for(j=0;j<num;j++)if(!G[i][vis[j]])break;if(j==num){//若為空，則皆與i相鄰，則此時(shí)將i加入到最大團(tuán)中vis[num]=i;if(dfs(i,num+1))return true;}}}if(num>res){//每添加一個(gè)點(diǎn)最多使最大團(tuán)數(shù)+1,后面的搜索就沒(méi)有意義了for(int i=0;i<num;i++)//最大團(tuán)的元素group[i]=vis[i];res=num;//最大團(tuán)中點(diǎn)的數(shù)目return true;}return false; } void maxClique(){res=-1;for(int i=n;i>0;i--){//枚舉所有點(diǎn)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);//最大團(tuán)的個(gè)數(shù)for(int i=0;i<res;i++)//最大團(tuán)中的頂點(diǎn)printf("%d ",group[i]);printf("\n");}return 0; }

【例題】

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

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

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。