第六章四色猜想及應用

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

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

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

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

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

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

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

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

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

＝3，其中3和’3都是G中點的3染色。這種枚舉法需要反復利用公式5.14計算極小點覆蓋，僅乘法次數(shù)超過2n。對于高階圖算法無效。22順序染色算法：設G＝(V,E)是簡單無向圖，V＝{x1,x2,...,xv}。1)令i＝1；2)令c＝1；3)若對任何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,