圖的著色問題.ppt

問題來源,圖的著色問題是由地圖的著色問題引申而來的：用m種顏色為地圖著色，使得地圖上的每一個區(qū)域著一種顏色，且相鄰區(qū)域顏色不同。問題處理：如果把每一個區(qū)域收縮為一個頂點(diǎn)，把相鄰兩個區(qū)域用一條邊相連接，就可以把一個區(qū)域圖抽象為一個平面圖。例如，圖12-1（a）所示的區(qū)域圖可抽象為12-1（b）所表示的平面圖。19世紀(jì)50年代，英國學(xué)者提出了任何地圖都可以4中顏色來著色的4色猜想問題。過了100多年，這個問題才由美國學(xué)者在計算機(jī)上予以證明，這就是著名的四色定理。例如，在圖12-1中，區(qū)域用城市名表示，顏色用數(shù)字表示，則圖中表示了不同區(qū)域的不同著色問題。,問題來源,圖的著色,通常所說的著色問題是指下述兩類問題：1給定無環(huán)圖G=(V,E)，用m種顏色為圖中的每條邊著色，要求每條邊著一種顏色，并使相鄰兩條邊有著不同的顏色，這個問題稱為圖的邊著色問題。2給定無向圖G=(V,E)，用m種顏色為圖中的每個頂點(diǎn)著色，要求每個頂點(diǎn)著一種顏色，并使相鄰兩頂點(diǎn)之間有著不同的顏色，這個問題稱為圖的頂著色問題。,頂點(diǎn)著色基本概念,獨(dú)立集：對圖G=(V,E)，設(shè)S是V的一個子集，若中任意兩個頂點(diǎn)在G中均不相鄰，則稱S為G的一個獨(dú)立集。最大獨(dú)立集：如果G不包含適合|S|S|的獨(dú)立集S，則稱S為G的最大獨(dú)立集。極大覆蓋：設(shè)K是G的一個獨(dú)立集，并且對于V-K的任一頂點(diǎn)v，K+v都不是G的獨(dú)立集，則稱K是G的一個極大覆蓋。極小覆蓋：極大獨(dú)立集的補(bǔ)集稱為極小覆蓋。V的子集K是G的極小覆蓋當(dāng)且僅當(dāng)：對于每個頂點(diǎn)v或者v屬于K，或者v的所有鄰點(diǎn)屬于K（但兩者不同時成立）。,頂點(diǎn)著色基本概念,K可著色：G的一個k頂點(diǎn)著色是指k種顏色1,2,k對于G各頂點(diǎn)的一個分配，如果任意兩個相鄰頂點(diǎn)都分配到不同的顏色，則稱著色是正常的。換句話說，無環(huán)圖G的一個正常k頂點(diǎn)著色是把V分成k個（可能有空的）獨(dú)立集的一個分類(V1,V2,Vk)。當(dāng)G有一個正常k頂點(diǎn)著色時，就成G是k頂點(diǎn)可著色的。G的色數(shù)X（G）是指G為k可著色的k的最小值，若X（G）=k，則稱G是k色的。事實(shí)上，如果我們將同色的頂點(diǎn)列入一個頂點(diǎn)子集，那么求X（G）就轉(zhuǎn)為求滿足下列條件的最少子集數(shù)k：（1）兩兩子集中的頂點(diǎn)不同；（2）子集中的兩兩頂點(diǎn)不相鄰。顯然有：（i）若G為平凡圖，則X（G）=1；（ii）若G為偶圖，則X（G）=2（iii）對任意圖G，有X（G）+1（這里表示為頂點(diǎn)數(shù)最大值）,頂點(diǎn)著色求頂色數(shù)的算法設(shè)計,我們由“每個同色頂點(diǎn)集合中的兩兩頂點(diǎn)不相鄰”可以看出，同色頂點(diǎn)集實(shí)際上是一個獨(dú)立集，當(dāng)我們用第1種顏色上色時，為了盡可能擴(kuò)大顏色1的頂點(diǎn)個數(shù)，逼近所用顏色數(shù)最少的目的，事實(shí)上就是找出圖G的一個極大獨(dú)立集并給它涂上顏色1。用第2種顏色上色時，同樣選擇另一個極大獨(dú)立集涂色，.，當(dāng)所有頂點(diǎn)涂色完畢，所用的顏色數(shù)即為所選的極大獨(dú)立集的個數(shù)。當(dāng)然，上述顏色數(shù)未必就是X（G），而且其和能夠含所有頂點(diǎn)的極大獨(dú)立集個數(shù)未必唯一。于是我們必須從一切若干極大獨(dú)立集的和含所有頂點(diǎn)的子集中，挑選所用極大獨(dú)立集個數(shù)最小者，其個數(shù)即為所用的顏色數(shù)X（G）。由此可以得算法步驟：Step1：求G圖的所有極大獨(dú)立集；Step2：求出一切若干極大獨(dú)立集的和含所有頂點(diǎn)的子集；Step3：從中挑選所用極大獨(dú)立集個數(shù)最小值，即為X（G）。,求極小覆蓋法布爾代數(shù)法,求極小覆蓋的方法-布爾代數(shù)法：對于每個頂點(diǎn)v，選擇v或者選擇v的所有鄰點(diǎn)。首先把“選擇頂點(diǎn)v”這個指令記為符號v，然后對給定的指令x和y，指令“x或y”和“x與y”分別記為x+y（邏輯和）和x.y（邏輯積）。例如，指令“選擇a與b，或者選擇b與c”記為ab+bc。從形式上看，邏輯和與邏輯積類似與集合的和，而且關(guān)于和成立的代數(shù)法則對于這兩個運(yùn)算也成立。布爾恒等式aa=aa+a=aa+ab=a如：,求極小覆蓋法布爾代數(shù)法,例1：求圖12-2G的頂色數(shù)解：Step1：求極大獨(dú)立集先求圖G的極小覆蓋，化簡得故G的極小覆蓋為取其補(bǔ)集，得到G的所有極大獨(dú)立集：Step2：求出一切若干極大獨(dú)立集和所有頂點(diǎn)的子集顯然我們可以選用4種顏色給每個頂點(diǎn)涂色，或者選用3種顏色分別給3個極大獨(dú)立集涂色，例如為b,d,f中的b、d、f涂顏色1，為a,f中的a涂顏色2，為a,c,g中的c和g涂顏色3，為a，e，g中的e涂顏色4。,求極小覆蓋法布爾代數(shù)法,Step3：從中挑選所用極大獨(dú)立集個數(shù)最小者，即為X（G）但上述子集的顏色數(shù)都不是X（G），正確的應(yīng)該是X（G）=3，該子集為：給b,d,f中的b,d,f涂顏色1，為a,e,g中a,e,g涂顏色2為a,c,g中的c涂顏色3。由此可見，求色數(shù)其需要求極大獨(dú)立集以及一切若干極大獨(dú)立集的和含所有頂點(diǎn)的子集，對于大圖，因?yàn)閳D計算量過大而成為實(shí)際上難以湊效的算法，所以不是一個好算法，一般我們采用貪心法等近似算法來求解。,窮舉法WelchPowell著色法,I將圖G中的結(jié)點(diǎn)按度數(shù)的遞減順序進(jìn)行排列(這種排列可能不是唯一的，因?yàn)橛行┙Y(jié)點(diǎn)的度數(shù)相同)。II用第一種顏色對第一結(jié)點(diǎn)著色，并按排列順序?qū)εc前面著色結(jié)點(diǎn)不鄰接的每一結(jié)點(diǎn)著上同樣的顏色。III用第二種顏色對尚未著色的結(jié)點(diǎn)重復(fù)II，用第三種顏色繼續(xù)這種做法，直到所有的結(jié)點(diǎn)全部著上色為止。,窮舉法WelchPowell著色法,給定圖G，用WelchPowell法對圖G著色,A4,A2,A3,A6,A5,3,2,1,1,3,窮舉法WelchPowell著色法,第一步：將圖G中的結(jié)點(diǎn)按度數(shù)的遞減順序排列：第二步：用第一種顏色對A5著第一種顏色，并對與A5不鄰接的結(jié)點(diǎn)A1也著第一種顏色。第三步：對結(jié)點(diǎn)A3及與A3不鄰接的結(jié)點(diǎn)A4、A8著第二種顏色。第四步：對結(jié)點(diǎn)A7及與A7不鄰接的結(jié)點(diǎn)A2、A6著第三種顏色?？梢?，圖G是三色的。但圖G不可能是二色的，因?yàn)锳1,A2,A3相互鄰接，故必須著三種顏色。所以x(G)=3。,回溯法,由于用m種顏色為無向圖G=(V,E)著色，其中，V的頂點(diǎn)個數(shù)為n，可以用一個n元組C=(c1,c2,cn)來描述圖的一種可能著色，其中，ci1,2,m，(1in)表示賦予頂點(diǎn)i的顏色。例如，5元組(1,2,2,3,1)表示對具有5個頂點(diǎn)的無向圖12.3（a）的一種著色，頂點(diǎn)1著顏色1，頂點(diǎn)2著顏色2，頂點(diǎn)3著顏色2，如此等等。如果在n元組C中，所有相鄰頂點(diǎn)都不會著相同顏色，就稱此n元組為可行解，否則為無效解?；厮莘ㄇ蠼鈭D著色問題：首先把所有頂點(diǎn)的顏色初始化為0，然后依次為每個頂點(diǎn)著色。如果其中i個頂點(diǎn)已經(jīng)著色，并且相鄰兩個頂點(diǎn)的顏色都不一樣，就稱當(dāng)前的著色是有效的局部著色；否則，就稱為無效的著色。如果由根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑上的著色，對應(yīng)于一個有效著色，并且路徑的長度小于n，那么相應(yīng)的著色是有效的局部著色。這時，就從當(dāng)前節(jié)點(diǎn)出發(fā)，繼續(xù)探索它的兒子節(jié)點(diǎn)，并把,回溯法,兒子結(jié)點(diǎn)標(biāo)記為當(dāng)前結(jié)點(diǎn)。在另一方面，如果在相應(yīng)路徑上搜索不到有效的著色，就把當(dāng)前結(jié)點(diǎn)標(biāo)記為d_結(jié)點(diǎn)，并把控制轉(zhuǎn)移去搜索對應(yīng)于另一種顏色的兄弟結(jié)點(diǎn)。如果對所有m個兄弟結(jié)點(diǎn)，都搜索不到一種有效的著色，就回溯到它的父親結(jié)點(diǎn)，并把父親結(jié)點(diǎn)標(biāo)記為d_結(jié)點(diǎn)，轉(zhuǎn)移去搜索父親結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。這種搜索過程一直進(jìn)行，直到根結(jié)點(diǎn)變?yōu)閐_結(jié)點(diǎn)，或者搜索路徑長度等于n，并找到了一個有效的著色為止。例：利用回溯法給下圖（a）著色。stepone:把5元組初始化為（0,0,0,0,0），從根結(jié)點(diǎn)開始向下搜索，以顏色1為頂點(diǎn)A著色，生成根結(jié)點(diǎn)2時，產(chǎn)生(1,0,0,0,0)，是個有效著色。,回溯法,回溯法,steptwo:以顏色1為頂點(diǎn)B著色生成結(jié)點(diǎn)3時，產(chǎn)生(1,1,0,0,0)，是個無效著色，結(jié)點(diǎn)3為d_結(jié)點(diǎn)。Stepthree：以顏色2為頂點(diǎn)B著色生成結(jié)點(diǎn)4，產(chǎn)生(1,2,0,0,0)，是個有效著色。Stepfour：分別以顏色1和2為頂點(diǎn)C著色生成結(jié)點(diǎn)5和6，產(chǎn)生(1,2,1,0,0)和(1,2,2,0,0)，都是無效著色，因此結(jié)點(diǎn)5和6都是d_結(jié)點(diǎn)。Stepfive：以顏色3為頂點(diǎn)C著色，產(chǎn)生(1,2,3,0,0)，是個有效著色。重復(fù)上述步驟，最后得到有效著色(1,2,3,3,1)。,回溯法,設(shè)數(shù)組colorn表示頂點(diǎn)的著色情況，回溯法求解m著色問題的算法如下：圖著色回溯法：1將數(shù)組colorn初始化為0；2k=1;3while(k=1)3.1依次考察每一種顏色，若頂點(diǎn)k的著色與其他頂點(diǎn)的著色不發(fā)生沖突，則轉(zhuǎn)步驟3.2；否則，搜索下一個顏色；3.2若頂點(diǎn)已全部著色，則輸出數(shù)組colorn，返回；3.3否則，3.3.1若頂點(diǎn)k是一個合法著色，則k=k+1，轉(zhuǎn)步驟3處理下一個頂點(diǎn)；3.3.2否則，重置頂點(diǎn)k的著色情況，k=k-1，轉(zhuǎn)步驟3。,回溯法,voidGraphColor(intn,intc,intm)/所有數(shù)組下標(biāo)從1開始for(i=1;i=1)colork=colork+1;while(colork=m)ifOk(k)break;elsecolork=colork+1;/搜索下一個顏色if(colork=m/回溯,回溯法,boolOk(intk)/判斷頂點(diǎn)k的著色是否發(fā)生沖突for(i=1;ik;i+)if(cki=1,貪心法,例如，圖12-4(a)所示的圖可以只用兩種顏色著色，將頂點(diǎn)1、3和4著成一種顏色，將頂點(diǎn)2和頂點(diǎn)5著成另外一種顏色。為簡單起見，下面假定k個顏色的集合為顏色1,顏色2,顏色k。（a）（b）,貪心法,貪心策略：選擇一種顏色，以任意頂點(diǎn)作為開始頂點(diǎn)，依次考察圖中的未被著色的每個頂點(diǎn)，如果一個頂點(diǎn)可以用顏色1著色，換言之，該頂點(diǎn)的鄰接點(diǎn)都還未被著色，則用顏色1為該頂點(diǎn)著色，當(dāng)沒有頂點(diǎn)能以這種顏色著色時，選擇顏色2和一個未被著色的頂點(diǎn)作為開始頂點(diǎn)，用第二種顏色為盡可能多的頂點(diǎn)著色，如果還有未著色的頂點(diǎn)，則選取顏色3并為盡可能多的頂點(diǎn)著色，依此類推，如圖12.4（b）所示。,設(shè)數(shù)組colorn表示頂點(diǎn)的著色情況，貪心法求解圖著色問題的算法如下：圖著色貪心法：1color1=1;/頂點(diǎn)1著顏色12for(i=2;i=n;i+)/其他所有頂點(diǎn)置未著色狀態(tài)colori=0;3k=0;4循環(huán)直到所有頂點(diǎn)均著色4.1k+;/取下一個顏色4.2for(i=2;i=n;i+)/用顏色k為盡量多的頂點(diǎn)著色4.2.1若頂點(diǎn)i已著色，則轉(zhuǎn)步驟4.2，考慮下一個頂點(diǎn);4.2.2若圖中與頂點(diǎn)i鄰接的頂點(diǎn)著色與頂點(diǎn)i著顏色k不沖突，則colori=k;5輸出k;,蟻群算法,設(shè)有k只螞蟻ai(i=1,2,k)分別代表k只螞蟻的初始城市，每一只螞蟻代表1種顏色，k只螞蟻分別遍歷所有的城市，ai采用隨機(jī)賦值的方法，城市用c=1,2,n表示，著色螞蟻的移動規(guī)則如圖12-5所示,蟻群算法,ai：表示第i只螞蟻的起始城市；pmax：螞蟻i下一步所選城市中最大的概率。建立鄰接矩陣Y為nn的矩陣，表示地區(qū)與地區(qū)之間的鄰接關(guān)系，Yic表示城市i與城市c的鄰接關(guān)系，當(dāng)城市i與城市c是同一個城市用Yic=0表示，當(dāng)城市i與城市c不相鄰，Yic取一較小值（如Yic=1）；當(dāng)城市i與城市c相鄰Yic取一較大值（如Yic=1）。ai與c城市的表更新方程：ai到c城市的概率計算公式：算法：Fort1將k只螞蟻隨機(jī)置于k個頂點(diǎn)上將k只螞蟻出發(fā)點(diǎn)置于當(dāng)前解集中Form1ton/kFori1tokForc1ton按概率pkic選擇頂點(diǎn)c移動螞蟻i到頂點(diǎn)c將頂點(diǎn)c置于螞蟻i的當(dāng)前解集檢查著色條件EndforEndfor檢查若未完成的任務(wù)Endfortt+1ic0Endfor輸出滿意h,圖著色問題的應(yīng)用安排考試問題,設(shè)學(xué)校共有n門功課需要進(jìn)行期末考試，因?yàn)椴簧賹W(xué)生不止選修一門課，所以不能把一個同學(xué)選修的兩門課安排在同一場次進(jìn)行考試。問學(xué)期的期末考試最少需要多少場次才能完成？,問題處理：我們以每門功課為一個頂點(diǎn)，當(dāng)且僅當(dāng)兩門功課被同一個學(xué)生選修時，在響應(yīng)兩個頂點(diǎn)之間連一條邊，得到一個圖G。我們將n門功課劃分成k個子集U1,U2,UK兩兩子集的功課都不相同。每個子集Ui（1ik）的頂點(diǎn)兩兩子集不相鄰，即子集內(nèi)的任意兩門功課都不能被一個學(xué)生選修。能這種要求劃分的子集數(shù)K必須最少，即不能劃分成k-1個子集。然后我們對每個子集內(nèi)的頂點(diǎn)涂一種顏色。同色頂點(diǎn)對應(yīng)的課程安排在同一場次考試，顏色數(shù)即為學(xué)期考試所需要的最少場次數(shù)。,圖著色問題的應(yīng)用安排考試問題,例：計算機(jī)系某學(xué)期開設(shè)了6門選修課程：數(shù)據(jù)倉庫與數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)導(dǎo)論，語音處理與壓縮編碼，數(shù)字媒體動畫設(shè)計技術(shù)，智能信息處理，入侵檢測技術(shù)，分別用a,b,c,d,e,f表示，我們以每門功課為一個頂點(diǎn)，當(dāng)且僅當(dāng)兩門功課被同一個學(xué)生選修時，在相應(yīng)兩個頂點(diǎn)之間連一條邊，學(xué)生選修情況如圖12-6所示：,圖著色問題的應(yīng)用安排考試問題,分析：利用求極小覆蓋的方法求得圖的一切極大獨(dú)立集如下：顯然我們可以選用6種顏色給每個頂點(diǎn)涂色，或者選用5種顏色分別給5個極大獨(dú)立集涂色，也可以選用4種顏色，例如I1中的a,c涂顏色，I2中的b,d涂顏色2，I3中的f涂顏色3，中的e涂顏色4。但上述方案的顏色數(shù)不是X（G），正確的答案應(yīng)該是X（G）=3有兩種方案：方案一：給I1中的a和c涂顏色1，I3中的b，f涂顏色2，I4中的d，e涂顏色3，故安排3場考試。第一場：數(shù)據(jù)倉庫與數(shù)據(jù)挖掘，智能信息處理第二場：機(jī)器學(xué)習(xí)，數(shù)字媒體動畫設(shè)計技術(shù)第三場：入侵檢測技術(shù)，語言處理與壓縮編碼。方案二：給I2中的b，d涂顏色1，給I5中的c，e涂顏色2，給I6中的a，f涂顏色3，故安排三場考試：第一場：機(jī)器學(xué)習(xí)，入侵檢測技術(shù)第二場：智能信息處理，語音處理與壓縮編碼第三場：數(shù)據(jù)倉庫與數(shù)據(jù)挖掘，數(shù)字媒體動畫設(shè)計,圖著色問題的應(yīng)用交通管理系統(tǒng),對于一個多叉路口，設(shè)計一個交通信號燈的管理系統(tǒng)：對車輛的可能行駛方向作某種分組，對分組的要求是使任一個組中各個方向行駛的車輛可以同時安全行駛而不發(fā)生碰撞。我們將通行方向作為結(jié)點(diǎn)，如果某些通行方向不能同時進(jìn)行，則在相應(yīng)的結(jié)點(diǎn)間連一條線于是問題就轉(zhuǎn)化為將結(jié)點(diǎn)分組，使得相連結(jié)點(diǎn)不在同一組里。例3：如圖12-7所示，某交叉路口有A，B，C，D，E,五條街道，請設(shè)計一個交通信號燈的管理系統(tǒng)。圖12-7分析：首先考慮可以通行的方向紅：AB，AC，AD，BA，DC，ED綠：DA，DB黃：EB，EC，EA藍(lán)：BC，BD,圖著色問題的應(yīng)用交通管理系統(tǒng),接下來的通行方向?yàn)榻Y(jié)點(diǎn)（如圖12-8所示），考慮結(jié)點(diǎn)分組,圖著色問題的應(yīng)用交通管理系統(tǒng),貪心算法設(shè)計：While有結(jié)點(diǎn)未著色選擇一種新顏色；在未著色的結(jié)點(diǎn)中，給盡可能的彼此結(jié)點(diǎn)之間沒有邊的點(diǎn)著色；NEW表示正確的，可以用新顏色著色的結(jié)點(diǎn)集合，從V1中找出可用新顏色著色的結(jié)點(diǎn)集的程序框架描述為New=For每個vV1doIfv與NEW中所有結(jié)點(diǎn)間沒有邊從V1中去掉v；NEW=NEWv；對圖和集合的操作：判斷一個集合是否為空：isSetEmpty（V1）置一個集合為空：emptySet（NEW）從集合中去掉一個元素：removeFromSet（）向集合里增加一個元素：addToSet（）,圖著色問題的應(yīng)用交通管理系統(tǒng),算法：檢查結(jié)點(diǎn)v與結(jié)點(diǎn)集合中結(jié)點(diǎn)之間在G中是否有邊連接IntcolorUp(GraphG)intcolor=0;V1=G.V;While(!isSetEmpty(V1)/判斷集合V1是否為空emptySet(NEW);/置集合NEW為空While(/檢查結(jié)點(diǎn)v與結(jié)點(diǎn)集合中結(jié)點(diǎn)之間在G中是否有邊連接addToSet(NEW,v);/向集合NEW里加元素vremoveFromSet(V1,v);/從集合V1中取掉元素v+color;return(color);,圖著色問題的應(yīng)用交通管理系統(tǒng),圖例中分組情況如下：綠色：AB，AC，AD，BA，DC，ED藍(lán)色：BC，BD，EA紅色：DA，DB黃色：EB，EC,一家公司制造n種化學(xué)制品C1,C2,Cn，其中某些制品是互不相容的，如果它們互相接觸，則會引起爆炸，作為一種預(yù)防措施，公司希望把它的倉庫分為間隔，以便把不相容的化學(xué)制品儲藏在不同的間隔里，試問：這個倉庫至少應(yīng)該分成幾個間隔？問題處理：構(gòu)造一個圖G，其頂點(diǎn)集是v1,v2,vn兩個頂點(diǎn)vi和vj相連當(dāng)且僅黨化學(xué)制品Ci和Cj互不相容，則倉庫的最小間隔數(shù)即為G的頂點(diǎn)數(shù)。,圖著色問題的應(yīng)用儲藏問題,無環(huán)圖G的一個k邊著色是指k種顏色對于G的各邊一個分配。若沒有兩條邊有著色相同的顏色，則稱著色是正常的。若G有正常的k邊著色，則稱k邊可著色的。若至少要用k種顏色（即可以正常k邊著色而不能k-1邊著色）時，則稱k為G的邊色數(shù)，記成。頂點(diǎn)v關(guān)聯(lián)的邊中有i色邊時，稱顏色i色在頂點(diǎn)v出現(xiàn)，在頂點(diǎn)i出現(xiàn)的顏色數(shù)目記成C（v）。通過邊頂對換法將圖G轉(zhuǎn)換為圖G：G圖中的邊e轉(zhuǎn)換為圖G中的一個頂點(diǎn)v；若圖G中兩條邊相鄰，則G中對應(yīng)兩個頂點(diǎn)之間連一條邊。然后對圖G進(jìn)行頂點(diǎn)著色或求頂色數(shù)x(G)，顯然：,邊著色邊頂對換法,例：求圖12-9G的邊色數(shù)將圖12-9G按邊頂對換法轉(zhuǎn)換為G(圖12-10)，用最少顏色數(shù)給G所有頂點(diǎn)上色的一種方案是，轉(zhuǎn)換成對圖G邊上色,邊著色邊頂對換法,問題描述：