圖的m著色問題.doc

5.8 圖的m著色問題1、問題描述給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著有不同顏色。這個(gè)問題是圖的m可著色判定問題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著有不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。 如圖1所示，圖G有N=5個(gè)頂點(diǎn)。圖的m著色問題即就是給定m種顏色，看是否有一種著色法使此圖中每條邊連接的2個(gè)頂點(diǎn)著有不同顏色。2 31 4 5圖1 問題描述圖解2、定義問題的解空間給定圖G=（V,E）和m種顏色，如果這個(gè)圖不是m可著色，給出否定回答；如果這個(gè)問題是m可著色的，找出所有不同的著色法。下面根據(jù)回溯法的遞歸描述框Backtrace設(shè)計(jì)圖的m著色算法。用圖的鄰接矩陣a表示無向連通圖G=(V,E)。若(i，j)屬于圖G=(V,E)的邊集E,則aij=1,否則aij=0。整數(shù)1，2，m用來表示m種不同顏色。頂點(diǎn)i所著的顏色用xi表示。數(shù)組x1:N是問題的解向量。問題的解空間可表示為一棵高度為N+1的完全m叉樹。N=3和m=2時(shí)的解空間樹如圖2所示。圖2 N=3和m=2時(shí)的解空間間樹解空間樹的第i(1=i=N)層中每一結(jié)點(diǎn)都有m個(gè)兒子，每個(gè)兒子相應(yīng)于xi的m個(gè)可能的著色之一。第N+1層結(jié)點(diǎn)均為葉結(jié)點(diǎn)。3、算法設(shè)計(jì)程序中出現(xiàn)的變量的含義：m：圖G可著顏色的種類；N：圖G的頂點(diǎn)個(gè)數(shù)；i,j,k：圖G的某一個(gè)頂點(diǎn)；sum：保存當(dāng)前已找到的可m著色的方案數(shù)；xi：保存頂點(diǎn)i所著的顏色。函數(shù)Ok檢查結(jié)點(diǎn)k是否可以著哪種顏色。bool Ok(int k) for(int j=1;jN) /當(dāng)tN時(shí)，算法搜索至葉結(jié)點(diǎn)，得到新的m著色方案，當(dāng)前找到的可m著色方案數(shù)sum加1 sum+; for(int i=1;i=N;i+) printf(“%3d”,xi); /輸出頂點(diǎn)i所著的顏色xi printf(“n”);else /當(dāng)t=N時(shí),當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間中的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有xi=1,2,m共m個(gè)兒子結(jié)點(diǎn)。對當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn)，由函數(shù)Ok檢查其可行性，并以深度優(yōu)先的方法遞歸地對可行子樹搜索，或剪去不可行子樹。 for(int i=1;i=m;i+) if(Ok(k,i) /判斷頂點(diǎn) k 是否可著顏色 i xk=i; Backtrace(k+1); /給頂點(diǎn) k+1查找可著的顏色 xk=0; /當(dāng)圖中所有的頂點(diǎn)都找到自己的可著顏色之后，依次 將 xN、xN-1、x1置0。 4、程序結(jié)果分析：當(dāng)輸入m=3時(shí)，對于圖1程序運(yùn)行結(jié)果如圖3所示。圖3 m=3時(shí)的運(yùn)行結(jié)果當(dāng)輸入m=4時(shí)，對于圖1程序運(yùn)行結(jié)果如圖4和圖5所示。圖4 m=4時(shí)的運(yùn)行結(jié)果之一圖5 m=4時(shí)的運(yùn)行結(jié)果之二5、算法效率分析圖m可著色問題的回溯法的計(jì)算時(shí)間上界可以通過計(jì)算解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)來估計(jì)。圖m可著色問題的解空間樹中內(nèi)結(jié)點(diǎn)個(gè)數(shù)是 。對于每一個(gè)內(nèi)結(jié)點(diǎn)，在最壞情況下，用函數(shù)Ok檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的每一個(gè)兒子所相應(yīng)的顏色的可用性需耗時(shí)O(mn)。因此，回溯法總的時(shí)間耗費(fèi)是 。6、圖的m著色問題習(xí)題講解給定無向連通圖G如圖6所示，只給3種顏色，如何給4個(gè)點(diǎn)著色，使有鄰邊關(guān)系的頂點(diǎn)顏色不同；共有多少種著色法？ 1 4 2 3圖6 無相連通圖G利用問題的解空間來分析此問題。圖的m著色問題的解空間可表示為一棵高度為5的完全3叉樹。以深度優(yōu)先的方法遞歸地對可行子樹搜索，或剪去不可行子樹。從而得出所有的解如圖7所示。 圖7 習(xí)題解答案7、參考資料l 數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏，吳偉民 編著/2007年03月/清華大學(xué)出版社l 算法設(shè)計(jì)與分析基礎(chǔ)(美)萊維丁 著，潘彥 譯/2007年01月/清華大學(xué)出版社 l 算法設(shè)計(jì)技巧與分析(沙特)阿蘇外耶 著，吳偉昶 等譯/2004年08月/電子工業(yè)出版社 l /suwei19870312/archive/