圖論第四章 平面圖及著色

1、第四章第四章 平面圖平面圖第一節(jié) 平面圖定義1 如果圖G能畫在曲面S上且使得它的邊僅在端點處相交，則稱G可嵌入曲面S。如果G可嵌入平面上，則稱G是是可平面圖可平面圖，已經(jīng)嵌入平面上的圖 稱為G G的平面表示的平面表示。 可平面圖G與G的平面表示 同構(gòu)，都簡稱為平面圖。(球極投影)GG定理定理1 1 圖G可嵌入球面圖G可嵌入平面。例例1 1 Q3是否可平面性？定義定義2 (平面圖的面平面圖的面,邊界和度數(shù)邊界和度數(shù)). 設(shè)G是一個平面圖，由G中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含G的結(jié)點，也不包含G的邊，這樣的區(qū)域稱為G的一個面的一個面。有界區(qū)域稱為內(nèi)部面稱為內(nèi)部面，無界區(qū)域稱為，無界區(qū)域稱為外部

2、面外部面。包圍面的長度最短的閉鏈稱為稱為該面的邊界該面的邊界。面的邊界的長度稱為稱為該面的度數(shù)該面的度數(shù)。例例2 指出下圖所示平面圖的面、面的邊界及指出下圖所示平面圖的面、面的邊界及面的度數(shù)。面的度數(shù)。e61234567e1e2e3e4e5e7e8e10e9f1f4f3f2f5解解:面f1,其邊界1e15e24e43e72e101,d(f1)=5. 面f2,其邊界1e102e87e91,d(f2)=3. 面f3,其邊界2e73e67e82,d(f3)=3. 面f4,其邊界3e44e57e63,d(f4)=3. 外部面f5, 其邊界1e15e24e36e34 e57e91,d(f5)=6.定理定

3、理2 對任何平面圖對任何平面圖G，面的度數(shù)之和面的度數(shù)之和是是邊數(shù)的二倍邊數(shù)的二倍。證明證明:對內(nèi)部面而言,因為其任何一條非割邊同時在兩個面中,故每增加一條邊圖的度數(shù)必增加2.對外部面的邊界,若某條邊不同時在兩個面中, 邊必為割邊,由于邊界是閉鏈,則該邊也為圖的度數(shù)貢獻2.從而結(jié)論成立.定理定理3 設(shè)設(shè)G是帶是帶v個頂點，個頂點，e條邊，條邊，r個面的連通的平個面的連通的平面圖，則面圖，則 v-e+r=2。（歐拉公式）。（歐拉公式）證明證明:(1)當當n=e=1時時,如下圖如下圖,結(jié)論顯然成立結(jié)論顯然成立.v=2,e=1,r=1v=1,e=1,r=2(2)下用數(shù)學(xué)歸納法證明下用數(shù)學(xué)歸納法證明.

4、 假設(shè)公式對n條邊的圖成立.設(shè)設(shè)G有有n+1條邊條邊.若G不含圈,任取一點x,從結(jié)點x開始沿路行走.因G不含圈,所以每次沿一邊總能達到一個新結(jié)點,最后會達到一個度數(shù)為1的結(jié)點,不妨設(shè)為a,在結(jié)點a不能再繼續(xù)前進.刪除結(jié)點a及其關(guān)聯(lián)的邊得圖G,G含有n條邊.由假設(shè)公式對G成立,而G比G多一個結(jié)點和一條邊,且G與G面數(shù)相同,故公式也適合于G. 若G含有圈C,設(shè)y是圈C上的一邊,則邊y一定是兩個不同面的邊界的一部分.刪除邊y得圖G,則G有n條邊.由假設(shè)公式對G成立，而G比G多一邊和多一面,G與G得頂點數(shù)相同.故公式也成立.推論推論1 設(shè)設(shè)G是帶是帶v個頂點，個頂點，e條邊的連通的平面簡條邊的連通的平

5、面簡單圖，其中單圖，其中v 3，則，則e 3v-6。證明證明:由于G是簡單圖,則G中無環(huán)和無平行邊.因此G的任何面的度數(shù)至少為3.故2e=d(f)3r (1) 其中r為G的面數(shù).由歐拉公式v-e+r=2所以r=2-v+e,代入(1)中有:2e3(2-v+e)即e3v-6。推論推論2 設(shè)設(shè)G是帶是帶v個頂點，個頂點，e條邊的連通的平面簡單圖，條邊的連通的平面簡單圖，其中其中v 3且沒有長度為且沒有長度為3的圈，則的圈，則e 2v-4。證明證明:因為圖G中沒有長度為3的圈,從而G的每個面的度數(shù)至少為4.因此有2e=d(f)4r (1)其中r為G的面數(shù).由歐拉公式v-e+r=2所以r=2-v+e,代

6、入(1)中有:2e4(2-v+e)即e2v-4。例例3 K5和和K3.3都是非平面圖。都是非平面圖。解解:圖圖K5有有5個頂點個頂點10條邊條邊,而而3*5-6=9,即即109,由由推論推論1知知,K5是非平面圖是非平面圖. 顯然顯然K3,3沒有長度為沒有長度為3的圈的圈,且有且有6個頂點個頂點9條邊條邊,因因而而92*6-4,由推論由推論2知知K3,3是非平面圖是非平面圖.推論推論3 設(shè)設(shè)G是帶是帶v個頂點，個頂點，e條邊，條邊，r個面的平面圖，個面的平面圖，則則 v- e+ r=1+w。其中。其中w為為G的連通分支數(shù)。的連通分支數(shù)。證明證明:由歐拉公式有: vi- ei+ ri=2(i=1

7、,2,w)從而有 vi- ei+ ri =2w又 vi=v, ei=e, ri =r+(w-1)(外部面被重復(fù)計算了w-1次.).所以有:V-e+r+(w-1)=2w整理即得: v- e+ r=1+w.推論推論4 設(shè)設(shè)G是任意平面簡單圖，則是任意平面簡單圖，則 (G) 5。證明證明:設(shè)G有v個頂點e條邊.若e6,結(jié)論顯然成立;若e6,假設(shè)G的每個頂點的度數(shù)6,則由推論1,有6v 2e 6v-12矛盾,所以 (G)5.例例4 平面上有平面上有n個頂點，其中任意兩個點之間的距離個頂點，其中任意兩個點之間的距離至少為至少為1.證明證明 在這在這n個點中距離恰好為個點中距離恰好為1的點對數(shù)的點對數(shù)至多

8、是至多是3n-6。證明證明:首先建立圖G=,其中V就取平面上給定的n個點(位置相同),當兩個頂點之間的距離為1時,兩頂點之間用一條直線段連接.顯然,圖G是一個n階簡單圖. 由推論1,只要證明G為一平面圖時即知結(jié)論成立. 反設(shè)G中存在兩條不同的邊a,b和x,y相交于非端點處o,如下圖(a)所示,其夾角為(0 ). 若 =,這時如下圖(b),顯然存在兩點距離小于1,與已知矛盾,從而0 .由于a到b的距離為1,x到y(tǒng)的距離為1,因此a,b,x,y中至少有兩個點,從交點o到這兩點的距離不超過1/2,不妨設(shè)為a,x,則點a與x之間的距離小于1,與已知矛盾,所以G中的邊除端點外不再有其它交點,即G為平面圖

9、.再據(jù)推論1,知結(jié)論成立.ayxbo (a)axby(b)第第2節(jié)節(jié) 庫拉圖斯基定理與極大平面庫拉圖斯基定理與極大平面定義定義1 設(shè)G是一個平面圖，通過刪除G的一條邊x、y,并增加一個新結(jié)點a和兩條邊x 、a與a、y（所獲得的任何圖也是平面圖），這樣的操作稱為初等細分初等細分。若可以從相同的圖G通過一系列初等細分來獲得圖G1和G2，稱稱G1和和G2是同胚的是同胚的. 如下圖G1,G2,G3是同胚的.G1G2G3定理定理1一個圖一個圖G是非平面的，是非平面的，當且僅當當且僅當它包含一個它包含一個同胚于同胚于K3.3或或K5的子圖。（證略）的子圖。（證略）例例1 說明彼得森圖不是平面圖。說明彼得森

10、圖不是平面圖。解解:刪去下圖刪去下圖(a)皮得森圖的結(jié)點皮得森圖的結(jié)點b,得其子圖得其子圖(b)H.而而H胚于胚于K3.3,所以皮得森不是平面圖所以皮得森不是平面圖.fdjeihabcdefghij(a)faedighjc(b)H(c)K3,3說明說明:庫拉圖斯基給出了平面圖的充要條件庫拉圖斯基給出了平面圖的充要條件,但用它并不能但用它并不能判別一個圖是否是平面圖的有效算法判別一個圖是否是平面圖的有效算法.定義定義2 設(shè)G是階大于等于3的簡單可平面圖，若在任意兩個不相鄰的結(jié)點vi,vj之間加入邊vi,vj，就會破壞圖的平面性，則稱G是極大平面圖是極大平面圖。極大平面圖的平面表示稱為表示稱為三角

11、剖三角剖分平面圖分平面圖.定理定理2. 極大平面圖的判別定理極大平面圖的判別定理:v階簡單平面圖G是極大平面圖的充要條件是充要條件是:（1）G中每個面的度數(shù)都是中每個面的度數(shù)都是3（2） G中有中有e條邊條邊r個面，則個面，則3r=2e（3）設(shè)）設(shè)G帶有帶有v個頂點，個頂點，e條邊，條邊，r個面則個面則 e=3v-6,r=2v-4.證明證明:必要性必要性:因G是簡單圖,故G中沒有環(huán)和平行邊,故不存在度數(shù)為1或2的面.假設(shè)G存在度數(shù)大于3的面f,不妨設(shè)為內(nèi)部面,如下圖G,顯然v1與v3不相鄰,在面f內(nèi)加入面v1,v3,圖G的平面性顯然沒有改變,這與圖G是極大平面圖矛盾.因此圖G的每個面的度數(shù)為3

12、,所以有3r=2e且e=3v-6,r=2v-4(歐拉公式) 充分性顯然充分性顯然.v2v1v5v3v4G定理定理2 設(shè)設(shè)G是簡單平面圖，則是簡單平面圖，則G有平面表示有平面表示 ，使使 中每條邊都是直線。中每條邊都是直線。證明證明:只要對極大平面圖G來證明定理即可(簡單平面圖是極大平面圖的子圖).當v=3時,G是三角形,定理顯然成立.假設(shè)定理對所有階數(shù)小于v的極大平面圖成立,并設(shè)G是三角剖分圖.選取xV(G)使x不是外部剖面邊界上的點.取邊x,y.則邊x,y僅是某兩個內(nèi)部三角形的公共邊.不妨設(shè)這兩個三角形分別為z1xy和z2xy.如圖(b)所示.收縮邊x,y,且結(jié)點x和y收縮為P,得圖G(圖c

13、).顯然G是平面圖,且有E(G)= E(G)-3=3(V(G)-1)-6= 3V(G)-9= 3V(G)-6,即G是v-1階極大平面圖,由歸納假設(shè),G有平面表示 GGG 使 的每條邊都是直線. 考慮 中邊Pz1和Pz2,將它分裂成兩個三角形(圖(b)和圖(c).這樣得到的圖 就是G的平面表示,而且每條邊都是直線段.定理得證.GGGz1z2z3xy(a)z1z2z3xy(b)z3z1z2p(c)凸多面體凸多面體 平面圖的理論與多面體的研究密切相關(guān)平面圖的理論與多面體的研究密切相關(guān):事實上事實上,由于每個凸多面體由于每個凸多面體P可以與一個連通可平面圖可以與一個連通可平面圖G對對應(yīng)應(yīng),G的頂點和邊

14、是的頂點和邊是P的頂點和棱的頂點和棱,那么那么G的每個頂點的度至少為3.由于由于G是一個平面圖是一個平面圖,則則P的面就是的面就是G的的面面,并且并且G的每一條邊落在兩個不同面的邊界上的每一條邊落在兩個不同面的邊界上. 一個多面體一個多面體P的頂點的頂點,棱和面的數(shù)目分別用棱和面的數(shù)目分別用V,E和和F來表示來表示,而且而且,這些分別是連通圖這些分別是連通圖G的頂點的頂點,邊和面的邊和面的數(shù)目數(shù)目.故故歐拉公式可寫成V-E+F=2,這就是著名的這就是著名的Euler凸多面體公式凸多面體公式. 為方便起見為方便起見,用用Vn和和Fn分別表示凸多面體分別表示凸多面體P的的n度度點和點和n度面的數(shù)目

15、度面的數(shù)目,則則n 3且且 332nnnnnFnVE多面體的一些性質(zhì)定理多面體的一些性質(zhì)定理定理定理3 每個凸多面體都至少有一個每個凸多面體都至少有一個n度面度面,其中其中3 n 5.證明證明:設(shè)F3=F4=F5=0,則即有F1/3E,又即V 2/3E,所以E=V+F-2 1/3E+2/3E-2=E-2.矛盾. 所以結(jié)論成立.FFFnFEnnnnnn666266633233nnnnEnVVV正多面體：每個面且每個多面角都相等的凸多面體。正多面體：每個面且每個多面角都相等的凸多面體。定理定理4 只有五個正多面體只有五個正多面體:四面體、立方體、十二面四面體、立方體、十二面體、八面體、二十面體體、

16、八面體、二十面體.證明證明:設(shè)P是正多面體且G是對應(yīng)的平面圖,對任何凸多面體均有: 因為P是正多面體,所以存在兩個正整數(shù)h(3)和k(3)使F=Fh且V=Vk,因此,有-8=(h-4)Fh+(k-4)Vk,且hFh=2E=kVk,因3h5.)4()4(4444224448333333nnnnnnnnnnnnVnFnFVnVnFFVEEFVE(1)當h=3時,有12=(6-k)Vk,由3k5.當k=3時,V3=4,F3=4,此時P是四面體.當k=4時,V4=6,F3=8,此時P是八面體當k=5時,V5=12,F3=20,此時P是十二面體(2)當h=4時,有8=(4-k)Vk,所以k=3,V3=8

17、,F4=6,即P是立方體.(3)當h=5時,有20=(10-3k)Vk,所以k=3,V3=20,F5=12,即P是十二面體.例例2 對哪些對哪些n,存在存在n條棱的凸多面體？條棱的凸多面體？解解:以多面體的頂點為圖的頂點,以多面體的棱為圖的邊,得到一個平面圖G,若p(G),q(G),f(G)分別表示G的頂點數(shù),邊數(shù)和面數(shù),則p(G)4, f(G) 4,且每個面的度數(shù)是3,由Euler公式易得q(G) 6,即沒有棱小于6的凸多面體.四面體是棱數(shù)為6的凸多面體.若有7條棱的凸多面體,則存在滿足上述條件, q(G) =7的平面圖,由Euler公式p(G) +f(G)= q(G)+2=9,但G的每個面

18、的度數(shù)至少是3,故2q(G)=G(m) 3f(G)(m為G的面),即f(G) (2/3)*q(G) =14/3又f(G)為整數(shù),所以f(G) 4,同理p(G) 4,所以p(G) +f(G) 8,矛盾.所以7條棱的凸多面體不存在. 現(xiàn)對k4,以k邊形為底的棱錐即有2k條棱的凸多面體進行討論.若把底為k-1邊形的棱錐中,底角處的一個三角面“鋸掉一個尖兒”,得到的是一個有2k+1條棱的凸多面體,總之,當n 6,n7時,才有n條棱的凸多面體.第三節(jié)第三節(jié) 圖的平面性檢測圖的平面性檢測定義1 圖G的H片: 設(shè)H是G的子圖，在E(G)-E(H)上定義二元關(guān)系R如下：xRy在G-E(H)中存在一條鏈W使得:

19、（1）W的第一條邊為x，最后一條邊為y；（2）W中只有兩個端點屬于H(即W的內(nèi)部點不屬于H). R是E(G)-E(H)上的等價關(guān)系。R確定E(G)-E(H)上的一個劃分設(shè)為S= S1、S2、Sm,由Si導(dǎo)出的 G-E(H)的子圖B1、B2、Bm 稱為G的H片。定義2. 若H1和H2都是圖G的子圖，稱V(H1) V(H2)為H1和H2在G中的接觸點集。記作VG(H1,H2).定義3 設(shè)H是可平面圖G的子圖， 是H的平面表示，若存在G的平面表示 ,使 稱 是G容許的。HHGHGGG容許的子圖G1非G容許的子圖G2 若B是G的H片，f是 的面,而且VG（B,H） ，稱B在f內(nèi)可畫出，其中 是f的邊界

20、。定理定理1 設(shè)設(shè) 是是G容許的，則對容許的，則對 的每一個片的每一個片B， 其中其中 證明證明:若若 是是G容許的容許的,則存在則存在G的一個平面表示的一個平面表示 .顯然顯然,H的片的片B所對應(yīng)的所對應(yīng)的 的子圖的子圖必然限制在 的一個面中,因此 . ( ,)GF B H H)(fBH)(fBHHH,)(, )(),(內(nèi)可畫出在且的面集為fBHHFHFffHBFGHGH),(HBFG, . .G st HG圖圖G的平面檢測的的平面檢測的DMP算法算法 DMP算法是由算法是由Demoucron,Malgrange,Pertuiset提供的提供的.在介紹該算法前在介紹該算法前,先對圖先對圖G進

21、行如下進行如下預(yù)處理預(yù)處理:(1)若G不連通,分別檢測每一個連通分支.當且僅當當且僅當所有的連通分支都是平面圖,G就是平面圖.(2)若G有割點,分別檢測每一塊.當且僅當每一塊是平面圖.(3)刪去G中的環(huán).(4)用一條邊代替G中2度點和與之相關(guān)聯(lián)的兩條邊.(5)刪去平行邊. 反復(fù)交錯使用(4)與(5),直到不能使用為止. 在做了上述簡化后,在簡單圖G中利用(6)和(7)兩個基本判斷法:(6)若若e9或或v3v-6或或 5,則則G不是平面圖不是平面圖.若不滿足(6)和(7),則需進一步檢測.DMP算法算法（1）設(shè)）設(shè)G1是是G中的圈，求出中的圈，求出G1 的平面表示的平面表示 。令。令i=1.（2

22、）若）若E(G)-E(Gi)= ，則停止。若，則停止。若E(G)-E(Gi) ,則確則確定定G的所有的所有Gi片，對每個片，對每個Gi片片B，求出集，求出集 （3）若存在）若存在Gi片片B使使 則停止，此時知則停止，此時知G是非平面是非平面圖。若存在圖。若存在Gi片片B使使 則令則令f= ;若不存若不存在這樣的片在這樣的片B，則令，則令B是任何一個是任何一個Gi片并任取片并任取 。 (4)選取一條選取一條xy路路Pi B使使x,y VG(B,Gi),令令Gi+1= Gi P,并把并把Pi畫在的畫在的 面面 f內(nèi)得內(nèi)得Gi+1的一個平面表示的一個平面表示 ，用，用i+1代替代替并轉(zhuǎn)入第并轉(zhuǎn)入第2

23、步。步。 1G),(iGGBF),(iGGBF( ,)1GiF BG ),(iGGBF),(iGGBFf iG1iG例1 利用DMP算法檢測圖G的平面性123456782134875613132661234276134第四節(jié)第四節(jié) 平面圖的著色平面圖的著色定義定義1 設(shè)G是無孤立結(jié)點的連通的平面圖，且G有K個面F1，F(xiàn)2，F(xiàn)k(包括外部面).則按下列過程作G的對偶圖G .（1）在G的每個面內(nèi)設(shè)置一個結(jié)點vi(1ik)。（2）過Fi與Fj的每一條公共邊ek作一條僅作一條邊vi,vj與ek相交。（3）當且僅當ek只是Fi的邊界時，vi恰有一自回路與ek相交。 這樣所得的圖G*稱為圖G的對偶圖.若G

24、*與G同構(gòu),稱G是自對偶的.如下圖G的對偶圖為圖中虛線.12341324定義定義2 圖的著色圖的著色是是對該圖的每個頂點都指定一種顏色，使沒有兩個相鄰的頂點頂點指定為相同的顏色。如果這些頂點選自于一個有k種顏色的集合，而不管k種顏色是否都用到，這樣的著色稱為稱為k著色著色。定義定義3 圖圖G的色數(shù)的色數(shù)是是著色這個圖G所需要的最少顏色數(shù)。記作記作 (G)。 圖G的色數(shù)也稱為也稱為圖圖G的點色數(shù)的點色數(shù).從定義可知從定義可知,對于對于G的任何子圖H,均有 (H) (G). 若G是n階完全圖,則則 (G)=n;若G是至少有一邊的二分圖,則則 (G)=2;若G是長為奇數(shù)的圈,則則 (G)=3. 當當

25、 (G) 3時時,G的特征至今尚未清楚的特征至今尚未清楚,在下一節(jié)在下一節(jié),將給出將給出G的色數(shù)的色數(shù) (G)的一個上界的一個上界.定理定理1 設(shè)設(shè)u和和v是圖是圖G中兩個不相鄰的頂點中兩個不相鄰的頂點,則則 (G)=min (G+u,v), (Gu,v) 其中其中Gu,v是把是把G中結(jié)點中結(jié)點u與與v重合成一個新結(jié)點，重合成一個新結(jié)點，且且G中分別與中分別與u與與v關(guān)聯(lián)的邊都與該新結(jié)點關(guān)聯(lián)。關(guān)聯(lián)的邊都與該新結(jié)點關(guān)聯(lián)。證明證明:記記e=u,v,（1）設(shè)）設(shè) (G)=k,并考慮G的K著色.假設(shè)頂點u與v染不同的顏色,則G的k著色也是G+e的k著色.此此時時 (G+e) k= (G).現(xiàn)假設(shè)頂點u

26、和v的染色相同,則G的一個k染色可得到Ge的一個染色.故(Ge)k= (G).又又在在G的的k染色中染色中,或者或者u與與v染為不同的顏色染為不同的顏色,或者為相同或者為相同的顏色的顏色,故故min (G+u,v), (Gu,v) (G). （2）G是G+e的子圖,顯然 (G) (G+e). 設(shè) (Ge)=k1,并把結(jié)點并把結(jié)點u和和v重合所得的新結(jié)點，記為重合所得的新結(jié)點，記為y,則在則在Ge的的k1著色中著色中,把分配給把分配給y的顏色分配給的顏色分配給G中中u和和v(u,v不相鄰不相鄰),即可得到即可得到G的一個的一個k1著色著色.故故 (G)k1= (Ge) 所以所以 (G) min

27、(G+e), (Gu,v). 綜合綜合(1)(2)所述所述,有有 (G)=min (G+u,v), (Gu,v). 四色問題四色問題:連通簡單平面圖的色數(shù)不超過4. 四色問題四色問題是蓋思里于1852年提出,后經(jīng)眾多數(shù)學(xué)家嘗試證明,均以失敗告終.1976年,美國數(shù)學(xué)家阿佩爾和黑肯宣布借助用計算機證明,但時間超過了1000小時,其可靠性仍在置疑之中. 定理定理2（五色定理）連通簡單平面圖（五色定理）連通簡單平面圖G的色數(shù)為不超過的色數(shù)為不超過5.證明證明:對圖的頂點數(shù)n作歸納. 當n5時,結(jié)論顯然.若n-1個頂點時結(jié)論成立.下證有n個頂點時結(jié)論也成立.由于G是平面圖,則(G) 5.故在G中至少存

28、在一個頂點v0,其度數(shù)d(v0) 5.在圖中刪去頂點v0得圖G,由歸納假設(shè)知G的色數(shù)為5.然后將v0又加回去,有兩種情況:(1)d(v0)5或d(v0)=5但和v0鄰接的5個結(jié)點的顏色數(shù)小于5.則v0極易著色,只要選擇與四周頂點不同的顏色著色即可.(2) d(v0)=5且和v0鄰接著的5個結(jié)點著的顏色的是5種顏色,如下圖(a)所示.稱G中所有紅黃色頂點為紅黃紅黃集集,稱G中所有黑白色頂點為黑白集黑白集.故又有兩種可能.(i)v1和v3屬于紅黃集導(dǎo)出子圖的兩個不同塊中,如下圖(b)所示.將v1所在塊的紅黃色對調(diào),并不影響G的正常著色.然后將v0著上紅色,即的圖G的正常著色.藍v3 黑v4v0黃v

29、3白v2紅v1(a)(b)(ii)v1和v3屬于紅黃集導(dǎo)出子圖的同一塊中,則v1和v3之間必有一條屬于紅黃集的路P,P加上結(jié)點v0可構(gòu)成圈C:v0v1pv3v0,如下圖(c)所示.由于C的存在,將黑白集分成兩個子集,一個在C內(nèi),一個在C外.于是問題轉(zhuǎn)化為(i)的類型,對黑白集按(i)型的辦法處理,即得圖G的正常著色.藍v3 黑v4v0黃v3白v2紅v1(b)(c)(a)例例1 求下圖求下圖G和和H的色數(shù)的色數(shù)acfgbedGHa:紅紅,b:藍藍,c:綠綠,d:紅紅,e:綠，綠，f:藍藍, g:紅紅(3色色)例例2. 由n(n3)個頂點v1,v2,vn以及邊v1,v2, v2,v3, , vn-

30、1,vn vn,v1 組成的圖稱為圈圖,記作Cn,試問圈圖的Cn的色數(shù)是多少.(分n為奇數(shù)，或偶數(shù)）例例3. Kn和和Km,n的色數(shù)分別是多少？的色數(shù)分別是多少？解解:由于Kn的每兩個頂點都相鄰,而當兩個相鄰的頂點必指定不同的顏色,故Kn的色數(shù)為n. Km,n的色數(shù)為2.用一種顏色著色m個頂點,用另一種顏色著色n個頂點.第五節(jié)第五節(jié) 圖著色的應(yīng)用圖著色的應(yīng)用 貯藏問題貯藏問題:某工廠生產(chǎn)n種化學(xué)制品c1,c2,cn,其中某些制品是互不相容.若它們相互接觸,則會發(fā)生化學(xué)反應(yīng)甚至引起爆炸,為安全起見,該工廠必須把倉庫分成若干隔間,以便把不相容的化學(xué)制品儲藏在不同的隔間,試問該倉庫至少應(yīng)分成幾個隔間

31、?解:構(gòu)建簡單圖G=,其中V(G)=c1,c2,cn 邊ci,cjE(G)化學(xué)制品ci與cj互不相容. 易知,倉庫的最少隔間數(shù)等于圖G的色數(shù)x(G).電視頻道分配問題 某地區(qū)內(nèi)有n家電視發(fā)射臺T1,T2,Tn.主管部門為每家電視發(fā)射臺分配一個頻道.為排除干擾,使用同一頻道的電視臺之間的距離必須大于指定的正數(shù)d,試問該地區(qū)至少需要多少頻道? 構(gòu)建簡單圖G=,其中V(G)=T1,T2,Tn 邊Ti, TjE(G)Ti與Tj之間距離d. 易知,需要的最少頻道等于圖G的色數(shù) (G).考試安排問題 某高校有n門選修課程v1,v2,vn需要進行期末考試.同一學(xué)生不能在同一天里參加兩門課程的考試.問學(xué)校的期

32、末考試需要幾天? 構(gòu)建簡單圖G=,其中V(G)=v1,v2,vn 邊vi, vjE(G)vi與vj被同一同學(xué)選修. 故考試需要的最小天數(shù)等于圖G的色數(shù) (G).變址寄存器 在有效的編譯器里,當把頻繁使用的變量暫時保存在中央處理單元而不是保存在常規(guī)內(nèi)存時,可以加速循環(huán)的執(zhí)行.對于給定的循環(huán)來說,需要多少個變址寄存器? 可以這樣建立模型:設(shè)圖里的每個頂點表示循環(huán)里的一個變量.若在循環(huán)執(zhí)行期間兩個頂點所表示的變量必須同時保存在變址寄存器里,則這兩個頂點之間有邊.因此,所需要的變址寄存器數(shù)就是該圖的色數(shù)所需要的變址寄存器數(shù)就是該圖的色數(shù).順序著色算法順序著色算法 到目前為止到目前為止,還沒有一個有效算

33、法來確定色數(shù)還沒有一個有效算法來確定色數(shù).順序著順序著色算法是一個求色算法是一個求 (G)的有效算法的有效算法:設(shè)設(shè)G=是簡單無是簡單無向圖，向圖，V=x1,x2xn用用N(xi)表示表示與與xi相鄰的全部頂點相鄰的全部頂點集合；對頂點集合；對頂點xi著色著色c，記為，記為 (xi)=c.(1)i:=1(2)c:=1(3)若對yN(xi),(y)c,則令(xi)=c并轉(zhuǎn)入第5步。(4)c:=c+1并轉(zhuǎn)入第3步。(5)若in，則i:=i+1并轉(zhuǎn)回第2步，否則停止.定理定理1 設(shè)設(shè)G是簡單連通圖，順序著色法產(chǎn)生是簡單連通圖，順序著色法產(chǎn)生G的頂點的頂點的一個的一個 (G）+1著色，所以著色，所以

34、(G)（G）+1(不證不證)證明證明:順序著色法用語言描述就是一次考慮每一頂點,將尚未指定給與其鄰接的頂點的最小顏色指定給該頂點,特別是決不能將兩個相鄰頂點指定為相同的顏色,因此順序著色算法確實產(chǎn)生一個頂點著色.最多存在個頂點與xi鄰接,故在x1,x2,xi-1中最多有個頂點xi鄰接.所以,當算法對頂點xi著色時,在顏色1,2, +1中至少有一種顏色尚未指定給與xi鄰接的頂點并且算法將這些顏色中最小的指定給xi,于是順序著色算法產(chǎn)生圖G的頂點的一個+1著色.例例1 試用順序著色法求圖試用順序著色法求圖G的色數(shù)。的色數(shù)。1211212121321211321212132121 定理定理1給出了連

35、通簡單圖給出了連通簡單圖G的色數(shù)的上界的色數(shù)的上界.1941年年R.L.Brooks證明了下面的定理證明了下面的定理.定理定理2. 設(shè)G是一個連通簡單圖,其頂點的最大度為.若G既不是完全圖Kn,也不是奇數(shù)圈圖Cn,則 (G) .第六節(jié)第六節(jié) 邊著色邊著色定義定義1 圖圖G的邊著色對的邊著色對G的每一條邊都的每一條邊都指定一個顏色，使得沒有兩個相鄰的邊都為同一種顏色。如果這些顏色都取自一個有K種顏色的集合，而不管這K種顏色是否都用掉，這樣的邊著色稱為稱為K邊著色。邊著色。定義定義2 圖圖G的邊著色數(shù)是的邊著色數(shù)是著色這個圖G需要的最少顏色數(shù)。記為記為 (G).邊著色轉(zhuǎn)化為點著色的方法：邊著色轉(zhuǎn)化

36、為點著色的方法： 邊著色可以轉(zhuǎn)化為相應(yīng)的點著色,即在邊著色圖中,將所有的邊對應(yīng)地轉(zhuǎn)化成點著色圖中的結(jié)點,結(jié)點轉(zhuǎn)化成相應(yīng)的邊.因此因此,由點著色性質(zhì)定理不難得到如下由點著色性質(zhì)定理不難得到如下定理定理.定理定理1 若若G是非空連通的簡單圖，是非空連通的簡單圖，G的最大頂點度為的最大頂點度為 ,則則 (G) +1。（不證）。（不證）圖的分類圖的分類:根據(jù)定理根據(jù)定理1,所有非空圖集可以分成兩類所有非空圖集可以分成兩類,若若 (G)= (G),則則G為為第一類圖第一類圖,否則稱為第二類圖否則稱為第二類圖.定理定理2 任意二分圖任意二分圖G是第一類圖。（不證）是第一類圖。（不證）K著色問題著色問題:已知一個圖已知一個圖G和和k種顏色的集合種顏色的集合:1,2,k,則存在圖則存在圖G的多少的多少k-著色著色?定義定義3. 圖G的不同k著色的數(shù)目，稱為稱為圖圖G的色多項的色多項式。式。記作記作f(G,k).說明說明:(1)若k0的最小k為G的色數(shù).(2)設(shè)mi是i種顏色對圖G的頂點進行著色的不同方案數(shù).用k(ki)種顏色對圖G進行著色,每取i種顏色時,共有miCki種不同的著色方案,故有:f(G,k)=m1Ck