第六章四色猜想及應(yīng)用

1面染色、四色猜想及染色理論的應(yīng)用問題2008年11月24日2面的k染色：平圖G中面的k染色是指k種顏色1,2，…，k對(duì)F(G)中元素的一種分配，使得有公共邊的兩個(gè)面顏色不同。換句話說，G中面的k染色是映射使得對(duì)每對(duì)i和j（1ijk），－1(i)與－1(j)無公共邊。若令則記6.3面染色*3面k色可染：若平圖G中存在一種k染色，則稱G中面k色可染。面色數(shù)：由定義可知，對(duì)任何平圖G有即平圖G的面染色數(shù)等于其幾何對(duì)偶圖的點(diǎn)染色數(shù)。由定理6.3和(6.6)式知，對(duì)任何平圖G，均有。于是一個(gè)自然的問題是：對(duì)每個(gè)平圖G是否有？4四色猜想2對(duì)任何平圖G均有。定理6.5下述三個(gè)命題等價(jià)：（1）每個(gè)平面圖中點(diǎn)4色可染（四色猜想1）；（2）每個(gè)平圖中面4色可染（四色猜想2）；（3）每個(gè)簡(jiǎn)單2邊連通3正則平面圖中邊3色可染。5任何地圖上的國(guó)家只須用4種顏色來染，使得任何具有共同邊界的兩個(gè)國(guó)家顏色都不相同。構(gòu)形：每個(gè)有界面的度都為3的平圖稱為構(gòu)形。圖6.11中的四個(gè)平圖都是構(gòu)形,分別記為O,P,Q,R。6.4四色猜想*6不可免完備集：設(shè)F

是由有限個(gè)構(gòu)形組成的集。若任何三角剖分圖至少含F(xiàn)中一個(gè)構(gòu)形，則稱F是不可免完備集。

由于任何平圖的最小度不超過5，所以F＝{O,P,Q,R}是一個(gè)不可免完備集。最小圖：若四色問題不成立，則由(6.6)式，必存在一些5色平圖，其中階數(shù)最小的稱為最小圖。G是最小圖，則，但對(duì)任何階數(shù)小于v(G)的平圖H均有。7Kempe企圖通過“證明”最小圖不存在來證明四色猜想。但是1890年P(guān).J.Heawood舉出了一個(gè)反例推翻了他的證明。設(shè)F是一個(gè)構(gòu)形，若它不含在任何一個(gè)最小圖中，則稱F為可約的。

Kempe實(shí)際上證明了構(gòu)形O,P,Q是可約的，但他沒有證明R也是可約的。然而他的這種思想提示人們：欲證四色猜想，只須尋找一個(gè)由可約構(gòu)形組成的不可免完備集。8

問題描述：在某所學(xué)校里，有m位教師x1,x2,...,xm和n個(gè)班級(jí)y1,y2,...,yn。在明確教師xi每周需要給班級(jí)yj上pij節(jié)課之后，要求制訂一張周課時(shí)盡可能少的總課表。這個(gè)問題稱為排課表問題。解決思路：構(gòu)作2部劃分為(X,Y)的2部分圖G，其中X＝{x1,x2,...,xm}，Y＝{y1,y2,...,yn}，xi與yj之間連有pij條邊。由于在任何一個(gè)課程時(shí)間段里，一位教師最多只能教一個(gè)班級(jí)，并且每個(gè)班級(jí)也最多只能由一位教師講課。所以，同一個(gè)課時(shí)（課程時(shí)間段）的課程表對(duì)應(yīng)圖G中的一個(gè)匹配。6.5排課表問題9反之，G中每個(gè)匹配對(duì)應(yīng)于同一課時(shí)（課程時(shí)間段）里教師們講課的一種可能安排。因此，排課表問題就是把E(G)劃分成匹配，而且使得匹配的數(shù)目盡可能地小，這個(gè)最小數(shù)目就是’(G)。由于G是2部分圖，所以

10若每個(gè)教師可以上的課時(shí)數(shù)<=p，且每個(gè)班級(jí)可以上的課時(shí)數(shù)<=p，則可用一張p課時(shí)的課表安排。進(jìn)一步，若僅有有限個(gè)教室，則如何安排？假設(shè)共l節(jié)課安排在p節(jié)課時(shí)的表中，則平均每課時(shí)開設(shè)l/p節(jié)課。（如每天8課時(shí)的上課時(shí)間段，有16節(jié)課要上，則每課時(shí)段開課為2課時(shí)，即同一時(shí)間段有兩個(gè)課堂在上課）11因此，某課程時(shí)段至少需要不小于[l/p]整數(shù)個(gè)教室，（如前所述需至少2個(gè)教室）。如下的定理6.6表明：在一張有p節(jié)課時(shí)（課程時(shí)間段）的課表中總能安排l節(jié)課使得在一節(jié)課時(shí)（課程時(shí)間段）內(nèi)最多占用不少于[l/p]整數(shù)的教室。12定理6.6設(shè)G是2部分圖且p，則G中存在p個(gè)不交匹配M1,M2,...,Mp，使得并對(duì)每個(gè)i(1ip)均有13例6.5.1設(shè)有4個(gè)教師和5個(gè)班級(jí)，要求矩陣P＝(pij)和一個(gè)可能采用的4節(jié)課時(shí)的課表如下所示：把對(duì)應(yīng)于P的2部分圖G的邊集E(G)劃分成一些匹配，可以用圖把該課表表示出來。1415從以上課表可以看出課程時(shí)段1中有4個(gè)班級(jí)在上課，表明需要4個(gè)教室。由定理6.6，對(duì)于p＝4的課程時(shí)段安排來說，E(G)中共有邊數(shù)＝11，使得該表可以排開，同時(shí)上課的課堂數(shù)為2或3（[11/4]）。問題：如果只有3個(gè)教室，是否能夠排開？對(duì)M1增廣路中的紅黑邊進(jìn)行互換，使得紅、黑邊均為3條，即可以在3個(gè)教室同時(shí)開3個(gè)課堂。16得到對(duì)應(yīng)的課程表如下：在這張課程表中任一課時(shí)內(nèi)只需要3個(gè)教室。假設(shè)只有兩個(gè)教室可供使用，定理6.6告訴我們必須有一張6節(jié)課時(shí)的課表才能滿足要求。課表如下：1718

某公司生產(chǎn)n種化學(xué)制品C1,C2,...,Cn，其中某些制品是互不相容的。若它們互相接觸，則會(huì)引起爆炸。作為一種預(yù)防措施，該公司希望把倉(cāng)庫(kù)分成若干隔間，以便把互不相容的化學(xué)制品貯藏在不同的隔間里。試問：這個(gè)倉(cāng)庫(kù)至少應(yīng)該分成幾個(gè)隔間？這個(gè)問題稱為貯藏問題。簡(jiǎn)單無向圖G＝(V,E)，其中V對(duì)應(yīng)各種化學(xué)制品，E中邊對(duì)應(yīng)互不相容的化學(xué)制品。倉(cāng)庫(kù)的最小隔間數(shù)等于G的色數(shù)(G)。6.6貯藏問題19

電視頻道分配問題，考試安排問題等都可以歸結(jié)為色數(shù)。規(guī)范k染色：設(shè)＝(V1,V2,...,Vk)是G中點(diǎn)的k染色，若V1是G的極大獨(dú)立集，V2是G－V1的極大獨(dú)立集，V3是G－(V1V2)的極大獨(dú)立集，依此類推，則稱是規(guī)范k染色。易證：G中點(diǎn)k色可染G有規(guī)范k染色20枚舉法：由于圖G的色數(shù)(G)是V(G)所能劃分成獨(dú)立集的最小數(shù)目，所以求出V(G)的所有獨(dú)立集劃分，然后比較這些劃分中獨(dú)立集的數(shù)目便可求出(G)。利用5.5節(jié)介紹的求極大獨(dú)立集的枚舉法就可以確定G的所有規(guī)范k染色。用于這些染色中顏色數(shù)的最小值即(G)。（由推理5.4.1

S是G的極大獨(dú)立集V(G)\S是G的極小點(diǎn)覆蓋。）21例6.6.1考察圖5.21所示的圖G。它有一個(gè)規(guī)范4染色和兩個(gè)規(guī)范3染色于是(G)

＝3，其中3和’3都是G中點(diǎn)的3染色。這種枚舉法需要反復(fù)利用公式5.14計(jì)算極小點(diǎn)覆蓋，僅乘法次數(shù)超過2n。對(duì)于高階圖算法無效。22順序染色算法：設(shè)G＝(V,E)是簡(jiǎn)單無向圖，V＝{x1,x2,...,xv}。1)令i＝1；2)令c＝1；3)若對(duì)任何yN(xi)，(y)c，則令(xi)=c并且轉(zhuǎn)入第5步；4)令c＝c+1，并轉(zhuǎn)回第3步；5)若i<v，則令i＝i+1，轉(zhuǎn)回第2步，否則停止。23例6.6.2考察如圖6.18(a)所示的圖G（即圖5.21）。該算法（按字母順序）的執(zhí)行步驟如圖6.18(b)－(h)所示。i＝1；c＝1；(b)1；(d)1；(a)＝124

i＝2；c＝1；(a)=1,(e)1,c=c+1=2;(a)2,(e)2,(b)=2。i＝3；c＝1；(b)1，(d)1，(e)1,(f)1,(c)＝1。25

i＝4；c＝1；(a)=1,c=c+1=2;(a)2,(c)2,(e)2,(d)=2。i＝5；c＝1；(c)=1,c=c+1=2;(b)=2,(d)=2,c=c+1=3;(b)3,(c)3,(d)3,(f)3,(b)=3。26

i＝6；c＝1；(c)=1,c=c+1=2;(c)2,