圖的著色問題.ppt

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