圖論第四章 平面圖及著色

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

2、面外部面。包圍面的長(zhǎng)度最短的閉鏈稱為稱為該面的邊界該面的邊界。面的邊界的長(zhǎng)度稱為稱為該面的度數(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 對(duì)任何平面圖對(duì)任何平面圖G，面的度數(shù)之和面的度數(shù)之和是是邊數(shù)的二倍邊數(shù)的二倍。證明證明:對(duì)內(nèi)部面而言,因?yàn)槠淙魏我粭l非割邊同時(shí)在兩個(gè)面中,故每增加一條邊圖的度數(shù)必增加2.對(duì)外部面的邊界,若某條邊不同時(shí)在兩個(gè)面中, 邊必為割邊,由于邊界是閉鏈,則該邊也為圖的度數(shù)貢獻(xiàn)2.從而結(jié)論成立.定理定理3 設(shè)設(shè)G是帶是帶v個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條邊，條邊，r個(gè)面的連通的平個(gè)面的連通的平面圖，則面圖，則 v-e+r=2。（歐拉公式）。（歐拉公式）證明證明:(1)當(dāng)當(dāng)n=e=1時(shí)時(shí),如下圖如下圖,結(jié)論顯然成立結(jié)論顯然成立.v=2,e=1,r=1v=1,e=1,r=2(2)下用數(shù)學(xué)歸納法證明下用數(shù)學(xué)歸納法證明.

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

5、面簡(jiǎn)單圖，其中單圖，其中v 3，則，則e 3v-6。證明證明:由于G是簡(jiǎn)單圖,則G中無(wú)環(huán)和無(wú)平行邊.因此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個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條邊的連通的平面簡(jiǎn)單圖，條邊的連通的平面簡(jiǎn)單圖，其中其中v 3且沒有長(zhǎng)度為且沒有長(zhǎng)度為3的圈，則的圈，則e 2v-4。證明證明:因?yàn)閳DG中沒有長(zhǎng)度為3的圈,從而G的每個(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個(gè)頂點(diǎn)個(gè)頂點(diǎn)10條邊條邊,而而3*5-6=9,即即109,由由推論推論1知知,K5是非平面圖是非平面圖. 顯然顯然K3,3沒有長(zhǎng)度為沒有長(zhǎng)度為3的圈的圈,且有且有6個(gè)頂點(diǎn)個(gè)頂點(diǎn)9條邊條邊,因因而而92*6-4,由推論由推論2知知K3,3是非平面圖是非平面圖.推論推論3 設(shè)設(shè)G是帶是帶v個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條邊，條邊，r個(gè)面的平面圖，個(gè)面的平面圖，則則 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ù)計(jì)算了w-1次.).所以有:V-e+r+(w-1)=2w整理即得: v- e+ r=1+w.推論推論4 設(shè)設(shè)G是任意平面簡(jiǎn)單圖，則是任意平面簡(jiǎn)單圖，則 (G) 5。證明證明:設(shè)G有v個(gè)頂點(diǎn)e條邊.若e6,結(jié)論顯然成立;若e6,假設(shè)G的每個(gè)頂點(diǎn)的度數(shù)6,則由推論1,有6v 2e 6v-12矛盾,所以 (G)5.例例4 平面上有平面上有n個(gè)頂點(diǎn)，其中任意兩個(gè)點(diǎn)之間的距離個(gè)頂點(diǎn)，其中任意兩個(gè)點(diǎn)之間的距離至少為至少為1.證明證明 在這在這n個(gè)點(diǎn)中距離恰好為個(gè)點(diǎn)中距離恰好為1的點(diǎn)對(duì)數(shù)的點(diǎn)對(duì)數(shù)至多

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

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

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

11、剖三角剖分平面圖分平面圖.定理定理2. 極大平面圖的判別定理極大平面圖的判別定理:v階簡(jiǎn)單平面圖G是極大平面圖的充要條件是充要條件是:（1）G中每個(gè)面的度數(shù)都是中每個(gè)面的度數(shù)都是3（2） G中有中有e條邊條邊r個(gè)面，則個(gè)面，則3r=2e（3）設(shè)）設(shè)G帶有帶有v個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e條邊，條邊，r個(gè)面則個(gè)面則 e=3v-6,r=2v-4.證明證明:必要性必要性:因G是簡(jiǎn)單圖,故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的每個(gè)面的度數(shù)為3

12、,所以有3r=2e且e=3v-6,r=2v-4(歐拉公式) 充分性顯然充分性顯然.v2v1v5v3v4G定理定理2 設(shè)設(shè)G是簡(jiǎn)單平面圖，則是簡(jiǎn)單平面圖，則G有平面表示有平面表示 ，使使 中每條邊都是直線。中每條邊都是直線。證明證明:只要對(duì)極大平面圖G來(lái)證明定理即可(簡(jiǎn)單平面圖是極大平面圖的子圖).當(dāng)v=3時(shí),G是三角形,定理顯然成立.假設(shè)定理對(duì)所有階數(shù)小于v的極大平面圖成立,并設(shè)G是三角剖分圖.選取xV(G)使x不是外部剖面邊界上的點(diǎn).取邊x,y.則邊x,y僅是某兩個(gè)內(nèi)部三角形的公共邊.不妨設(shè)這兩個(gè)三角形分別為z1xy和z2xy.如圖(b)所示.收縮邊x,y,且結(jié)點(diǎn)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,將它分裂成兩個(gè)三角形(圖(b)和圖(c).這樣得到的圖 就是G的平面表示,而且每條邊都是直線段.定理得證.GGGz1z2z3xy(a)z1z2z3xy(b)z3z1z2p(c)凸多面體凸多面體 平面圖的理論與多面體的研究密切相關(guān)平面圖的理論與多面體的研究密切相關(guān):事實(shí)上事實(shí)上,由于每個(gè)凸多面體由于每個(gè)凸多面體P可以與一個(gè)連通可平面圖可以與一個(gè)連通可平面圖G對(duì)對(duì)應(yīng)應(yīng),G的頂點(diǎn)和邊

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

15、度面的數(shù)目,則則n 3且且 332nnnnnFnVE多面體的一些性質(zhì)定理多面體的一些性質(zhì)定理定理定理3 每個(gè)凸多面體都至少有一個(gè)每個(gè)凸多面體都至少有一個(gè)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正多面體：每個(gè)面且每個(gè)多面角都相等的凸多面體。正多面體：每個(gè)面且每個(gè)多面角都相等的凸多面體。定理定理4 只有五個(gè)正多面體只有五個(gè)正多面體:四面體、立方體、十二面四面體、立方體、十二面體、八面體、二十面體體、

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

17、,F4=6,即P是立方體.(3)當(dāng)h=5時(shí),有20=(10-3k)Vk,所以k=3,V3=20,F5=12,即P是十二面體.例例2 對(duì)哪些對(duì)哪些n,存在存在n條棱的凸多面體？條棱的凸多面體？解解:以多面體的頂點(diǎn)為圖的頂點(diǎn),以多面體的棱為圖的邊,得到一個(gè)平面圖G,若p(G),q(G),f(G)分別表示G的頂點(diǎn)數(shù),邊數(shù)和面數(shù),則p(G)4, f(G) 4,且每個(gè)面的度數(shù)是3,由Euler公式易得q(G) 6,即沒有棱小于6的凸多面體.四面體是棱數(shù)為6的凸多面體.若有7條棱的凸多面體,則存在滿足上述條件, q(G) =7的平面圖,由Euler公式p(G) +f(G)= q(G)+2=9,但G的每個(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)對(duì)k4,以k邊形為底的棱錐即有2k條棱的凸多面體進(jìn)行討論.若把底為k-1邊形的棱錐中,底角處的一個(gè)三角面“鋸掉一個(gè)尖兒”,得到的是一個(gè)有2k+1條棱的凸多面體,總之,當(dāng)n 6,n7時(shí),才有n條棱的凸多面體.第三節(jié)第三節(jié) 圖的平面性檢測(cè)圖的平面性檢測(cè)定義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中只有兩個(gè)端點(diǎn)屬于H(即W的內(nèi)部點(diǎn)不屬于H). R是E(G)-E(H)上的等價(jià)關(guān)系。R確定E(G)-E(H)上的一個(gè)劃分設(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中的接觸點(diǎn)集。記作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容許的，則對(duì)容許的，則對(duì) 的每一個(gè)片的每一個(gè)片B， 其中其中 證明證明:若若 是是G容許的容許的,則存在則存在G的一個(gè)平面表示的一個(gè)平面表示 .顯然顯然,H的片的片B所對(duì)應(yīng)的所對(duì)應(yīng)的 的子圖的子圖必然限制在 的一個(gè)面中,因此 . ( ,)GF B H H)(fBH)(fBHHH,)(, )(),(內(nèi)可畫出在且的面集為fBHHFHFffHBFGHGH),(HBFG, . .G st HG圖圖G的平面檢測(cè)的的平面檢測(cè)的DMP算法算法 DMP算法是由算法是由Demoucron,Malgrange,Pertuiset提供的提供的.在介紹該算法前在介紹該算法前,先對(duì)圖先對(duì)圖G進(jìn)

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

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

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

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

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

26、和v的染色相同,則G的一個(gè)k染色可得到Ge的一個(gè)染色.故(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é)點(diǎn)并把結(jié)點(diǎn)u和和v重合所得的新結(jié)點(diǎn)，記為重合所得的新結(jié)點(diǎn)，記為y,則在則在Ge的的k1著色中著色中,把分配給把分配給y的顏色分配給的顏色分配給G中中u和和v(u,v不相鄰不相鄰),即可得到即可得到G的一個(gè)的一個(gè)k1著色著色.故故 (G)k1= (Ge) 所以所以 (G) min

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

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

29、3白v2紅v1(a)(b)(ii)v1和v3屬于紅黃集導(dǎo)出子圖的同一塊中,則v1和v3之間必有一條屬于紅黃集的路P,P加上結(jié)點(diǎn)v0可構(gòu)成圈C:v0v1pv3v0,如下圖(c)所示.由于C的存在,將黑白集分成兩個(gè)子集,一個(gè)在C內(nèi),一個(gè)在C外.于是問題轉(zhuǎn)化為(i)的類型,對(duì)黑白集按(i)型的辦法處理,即得圖G的正常著色.藍(lán)v3 黑v4v0黃v3白v2紅v1(b)(c)(a)例例1 求下圖求下圖G和和H的色數(shù)的色數(shù)acfgbedGHa:紅紅,b:藍(lán)藍(lán),c:綠綠,d:紅紅,e:綠，綠，f:藍(lán)藍(lán), g:紅紅(3色色)例例2. 由n(n3)個(gè)頂點(diǎn)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的每?jī)蓚€(gè)頂點(diǎn)都相鄰,而當(dāng)兩個(gè)相鄰的頂點(diǎn)必指定不同的顏色,故Kn的色數(shù)為n. Km,n的色數(shù)為2.用一種顏色著色m個(gè)頂點(diǎn),用另一種顏色著色n個(gè)頂點(diǎn).第五節(jié)第五節(jié) 圖著色的應(yīng)用圖著色的應(yīng)用 貯藏問題貯藏問題:某工廠生產(chǎn)n種化學(xué)制品c1,c2,cn,其中某些制品是互不相容.若它們相互接觸,則會(huì)發(fā)生化學(xué)反應(yīng)甚至引起爆炸,為安全起見,該工廠必須把倉(cāng)庫(kù)分成若干隔間,以便把不相容的化學(xué)制品儲(chǔ)藏在不同的隔間,試問該倉(cāng)庫(kù)至少應(yīng)分成幾個(gè)隔間

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

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

33、法來(lái)確定色數(shù)還沒有一個(gè)有效算法來(lái)確定色數(shù).順序著順序著色算法是一個(gè)求色算法是一個(gè)求 (G)的有效算法的有效算法:設(shè)設(shè)G=是簡(jiǎn)單無(wú)是簡(jiǎn)單無(wú)向圖，向圖，V=x1,x2xn用用N(xi)表示表示與與xi相鄰的全部頂點(diǎn)相鄰的全部頂點(diǎn)集合；對(duì)頂點(diǎn)集合；對(duì)頂點(diǎn)xi著色著色c，記為，記為 (xi)=c.(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)若in，則i:=i+1并轉(zhuǎn)回第2步，否則停止.定理定理1 設(shè)設(shè)G是簡(jiǎn)單連通圖，順序著色法產(chǎn)生是簡(jiǎn)單連通圖，順序著色法產(chǎn)生G的頂點(diǎn)的頂點(diǎn)的一個(gè)的一個(gè) (G）+1著色，所以著色，所以

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

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

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