《圖的著色問題》PPT課件.ppt

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