平面圖及圖的著色

1、8.6 平面圖平面圖離離 散散 數(shù)數(shù) 學(xué)學(xué)周金明周金明說明說明平面圖的基本概念平面圖的基本概念歐拉公式歐拉公式平面圖的判斷平面圖的判斷平面圖的對(duì)偶圖平面圖的對(duì)偶圖頂點(diǎn)著色及點(diǎn)色數(shù)頂點(diǎn)著色及點(diǎn)色數(shù)地圖的著色與平面圖的點(diǎn)著色地圖的著色與平面圖的點(diǎn)著色8.1 平面圖的基本概念平面圖的基本概念一、關(guān)于平面圖的一些基本概念一、關(guān)于平面圖的一些基本概念1、 平面圖的定義平面圖的定義定義定義8.18.1 q G可嵌入曲面可嵌入曲面S如果圖如果圖G能以這樣的方式畫在曲面能以這樣的方式畫在曲面S上上，即除頂點(diǎn)處外無邊相交。，即除頂點(diǎn)處外無邊相交。 q G是可平面圖或平面圖是可平面圖或平面圖若若G可嵌入平面可嵌入

2、平面。q G的平面嵌入的平面嵌入畫出的無邊相交的平面圖。畫出的無邊相交的平面圖。q 非平面圖非平面圖無平面嵌入的圖。無平面嵌入的圖。（2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。2、 幾點(diǎn)說明及一些簡單結(jié)論幾點(diǎn)說明及一些簡單結(jié)論q 一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時(shí)，一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時(shí)，一定是指平面嵌入。一定是指平面嵌入。q K5和和K3,3都不是平面圖。都不是平面圖。q 定理定理8.1 8.1 設(shè)設(shè)GG，若若G為平面圖，則為平面圖，則G 也是平面圖。也是平面圖。q 定理定理8.2 8.2 設(shè)設(shè)GG，

3、若若G 為非平面圖，則為非平面圖，則G也是非平面圖。也是非平面圖。q 推論推論 Kn(n 5)和和K3,n(n 3)都是非平面圖。都是非平面圖。q 定理定理8.3 8.3 若若G為平面圖，則在為平面圖，則在G中加平行邊或環(huán)所得圖還是中加平行邊或環(huán)所得圖還是平面圖。平面圖。即平行邊和環(huán)不影響圖的平面性。即平行邊和環(huán)不影響圖的平面性。 二、平面圖的面與次數(shù)（針對(duì)平面圖的平面嵌入）二、平面圖的面與次數(shù)（針對(duì)平面圖的平面嵌入）1、 定義定義定義定義8.28.2 設(shè)設(shè)G是平面圖，是平面圖，q G的面的面由由G的邊將的邊將G所在的平面劃分成的每一個(gè)區(qū)域。所在的平面劃分成的每一個(gè)區(qū)域。q 無限面（外部面）無

4、限面（外部面）面積無限的面，記作面積無限的面，記作R0。q 有限面（內(nèi)部面）有限面（內(nèi)部面）面積有限的面面積有限的面 ，記作，記作R1, R2, , Rk。q 面面Ri的邊界的邊界包圍面包圍面Ri的所有邊組成的回路組。的所有邊組成的回路組。q 面面Ri的次數(shù)的次數(shù)Ri邊界的長度，記作邊界的長度，記作deg(Ri)。2、幾點(diǎn)說明、幾點(diǎn)說明q 若平面圖若平面圖G有有k個(gè)面，可籠統(tǒng)地用個(gè)面，可籠統(tǒng)地用R1, R2, , Rk表示，不需表示，不需要指出外部面。要指出外部面。q 回路組是指：邊界可能是初級(jí)回路（圈），可能是簡單回回路組是指：邊界可能是初級(jí)回路（圈），可能是簡單回路，也可能是復(fù)雜回路。特別

5、地，還可能是非連通的回路路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路之并。之并。平面圖有平面圖有4個(gè)面，個(gè)面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1R2R3R0定理定理8.48.4 平面圖平面圖G中所有面的次數(shù)之和等于邊數(shù)中所有面的次數(shù)之和等于邊數(shù)m的兩倍，即的兩倍，即 本定理中所說平面圖是指平面嵌入。本定理中所說平面圖是指平面嵌入。 eE(G)，當(dāng)當(dāng)e為面為面Ri和和Rj(ij)的公共邊界上的邊時(shí)，在計(jì)算的公共邊界上的邊時(shí)，在計(jì)算Ri和和Rj的次的次數(shù)時(shí)，數(shù)時(shí)，e各提供各提供1。當(dāng)當(dāng)e只在某一個(gè)面的邊界上出現(xiàn)時(shí)，則在計(jì)算該面的次數(shù)時(shí)

6、只在某一個(gè)面的邊界上出現(xiàn)時(shí)，則在計(jì)算該面的次數(shù)時(shí)，e提供提供2。于是每條邊在計(jì)算總次數(shù)時(shí)，都提供于是每條邊在計(jì)算總次數(shù)時(shí)，都提供2，因而，因而deg(Ri)=2m。1deg()2riiRmrG其中 為 的面數(shù)證證明明三、極大平面圖三、極大平面圖1、 定義定義定義定義8.38.3 若在簡單平面圖若在簡單平面圖G中的任意兩個(gè)不相鄰的頂點(diǎn)之間中的任意兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖，則稱加一條新邊所得圖為非平面圖，則稱G為極大平面圖。為極大平面圖。注意：注意：若簡單平面圖若簡單平面圖G中已無不相鄰頂點(diǎn)，中已無不相鄰頂點(diǎn)，G顯然是極大平顯然是極大平面圖，如面圖，如K1（平凡圖）平凡圖）,

7、 K2, K3, K4都是極大平面圖。都是極大平面圖。2、極大平面圖的主要性質(zhì)、極大平面圖的主要性質(zhì)定理定理8.58.5 極大平面圖是連通的。極大平面圖是連通的。定理定理8.68.6 n(n 3)階極大平面圖中不可能有割點(diǎn)和橋。階極大平面圖中不可能有割點(diǎn)和橋。定理定理8.78.7 設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖為極大平面圖當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為的每個(gè)面的次數(shù)均為3。q本節(jié)只證明必要性，即本節(jié)只證明必要性，即設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖，則為極大平面圖，則G的每個(gè)面的次數(shù)均為的每個(gè)

8、面的次數(shù)均為3。q由于由于n 3, 又又G必為簡單平面圖，可知，必為簡單平面圖，可知，G每個(gè)面的次數(shù)均每個(gè)面的次數(shù)均 3。q因?yàn)橐驗(yàn)镚為平面圖，又為極大平面圖?？勺C為平面圖，又為極大平面圖?？勺CG不可能存在次數(shù)不可能存在次數(shù)3的面。的面。證證明明思思路路假設(shè)存在面假設(shè)存在面Ri的次數(shù)的次數(shù)deg(Ri)=s4，如圖所示。如圖所示。在在G中，若中，若v1與與v3不相鄰，在不相鄰，在Ri內(nèi)加邊內(nèi)加邊(v1,v3)不破壞平面性，這不破壞平面性，這與與G是極大平面圖矛盾，因而是極大平面圖矛盾，因而v1與與v3必相鄰，由于必相鄰，由于Ri的存在，的存在，邊邊(v1,v3)必在必在Ri外。外。 類似地，類

9、似地，v2與與v4也必相鄰，且邊也必相鄰，且邊(v2,v4)也必在也必在Ri外部，于是必外部，于是必產(chǎn)生產(chǎn)生(v1,v3)與與(v2,v4)相交于相交于Ri的外部，這又矛盾于的外部，這又矛盾于G是平面圖，是平面圖，所以必有所以必有s3，即即G中不存在次數(shù)大于或等于中不存在次數(shù)大于或等于4的面，所以的面，所以G的的每個(gè)面為每個(gè)面為3條邊所圍，也就是各面次數(shù)均為條邊所圍，也就是各面次數(shù)均為3。sS-1 只有右邊的圖為極大平面圖。只有右邊的圖為極大平面圖。 因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為3。 四、極小非平面圖四、極小非平面圖定義定義8.48.4 若在非平面圖若在非平面圖G中

10、任意刪除一條邊，所得圖中任意刪除一條邊，所得圖G為平面為平面圖，則稱圖，則稱G為極小非平面圖。為極小非平面圖。由定義不難看出：由定義不難看出：q K5, K3,3都是極小非平面圖。都是極小非平面圖。q 極小非平面圖必為簡單圖。極小非平面圖必為簡單圖。例如：例如：以下各圖均為極小非平面圖。以下各圖均為極小非平面圖。小節(jié)結(jié)束小節(jié)結(jié)束8.2 8.2 歐拉公式歐拉公式 一、歐拉公式相關(guān)定理一、歐拉公式相關(guān)定理1、 歐拉公式歐拉公式定理定理8.8 8.8 對(duì)于任意的連通的平面圖對(duì)于任意的連通的平面圖G，有有n-m+r=2其中，其中，n、m、r分別為分別為G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。 證

11、明證明對(duì)邊數(shù)對(duì)邊數(shù)m作歸納法。作歸納法。 (1) m0時(shí)，由于時(shí)，由于G為連通圖，所以為連通圖，所以G只能是由一個(gè)孤立頂只能是由一個(gè)孤立頂點(diǎn)組成的平凡圖，即點(diǎn)組成的平凡圖，即n=1，m=0，r=1，結(jié)論顯然成立。結(jié)論顯然成立。(2) m1時(shí)，由于時(shí)，由于G為連通圖，所以為連通圖，所以n=2，m=1，r=1，結(jié)論結(jié)論顯然成立。顯然成立。(3)設(shè)設(shè)mk(k1)時(shí)成立，當(dāng)時(shí)成立，當(dāng)mk+1時(shí)，對(duì)時(shí)，對(duì)G進(jìn)行如下討論。進(jìn)行如下討論。q 若若G是樹，則是樹，則G是非平凡的，因而是非平凡的，因而G中至少有兩片樹葉。中至少有兩片樹葉。 設(shè)設(shè)v為樹葉，令為樹葉，令G=G-v，則則G仍然是連通圖，且仍然是連通圖

12、，且G的邊數(shù)的邊數(shù)m=m-1=k，n=n-1，r=r。 由假設(shè)可知由假設(shè)可知 n-m+r=2，式中式中n，m，r分別為分別為G的頂點(diǎn)數(shù)，的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。邊數(shù)和面數(shù)。 于是于是n-m+r=(n+1)-(m+1)+r=n-m+r=2q 若若G不是樹，則不是樹，則G中含圈。中含圈。 設(shè)邊設(shè)邊e在在G中某個(gè)圈上，令中某個(gè)圈上，令G=G-e，則則G仍連通且仍連通且m=m-1=k， n=n，r=r-1。 由假設(shè)有由假設(shè)有 n-m+r=2。 于是于是 n-m+r=n-(m+1)-(r+1)=n-m+r=2 定理定理8.9 8.9 對(duì)于具有對(duì)于具有k(k2)個(gè)連通分支的平面圖個(gè)連通分支的平面圖G，有有

13、n-m+r = k+1其中其中n，m，r分別為分別為G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。 證明證明 設(shè)設(shè)G的連通分支分別為的連通分支分別為G1、G2、Gk，并設(shè)并設(shè)Gi的頂點(diǎn)數(shù)、邊的頂點(diǎn)數(shù)、邊數(shù)、面數(shù)分別為數(shù)、面數(shù)分別為ni、mi、ri、i=1，2，k。 由歐拉公式可知由歐拉公式可知: ni-mi+ri = 2，i=1，2，k (8.1)易知，易知，11kkiiiimmnn，由于每個(gè)由于每個(gè)Gi 有一個(gè)外部面，而有一個(gè)外部面，而G只有一個(gè)外部面，所以只有一個(gè)外部面，所以G的面數(shù)的面數(shù)11kiirrk于是，于是，對(duì)對(duì)(8.1)的兩邊同時(shí)求和得的兩邊同時(shí)求和得 11112()1kkkki

14、iiiiiiiiiknmrnmrnmrk 經(jīng)整理得經(jīng)整理得 n-m+r = k+1。2、 與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理定理定理8.108.10 設(shè)設(shè)G為連通的平面圖，且每個(gè)面的次數(shù)至少為為連通的平面圖，且每個(gè)面的次數(shù)至少為l(l3)，則則 G的邊數(shù)與頂點(diǎn)數(shù)有如下關(guān)系：的邊數(shù)與頂點(diǎn)數(shù)有如下關(guān)系：由定理由定理8.4（面的次數(shù)之和等于邊數(shù)的（面的次數(shù)之和等于邊數(shù)的2倍）及歐拉公式得倍）及歐拉公式得(2)2lmnl證明證明12deg()(2)riimRl rlmn 解得解得 (2)2lmnl推論推論 K5, K3,3不是平面圖。不是平面圖。證明證明q若若K5是平面圖，由于是平面圖，由于K5

15、中無環(huán)和平行邊，所以每個(gè)面的次數(shù)中無環(huán)和平行邊，所以每個(gè)面的次數(shù)均大于或等于均大于或等于l3，由由定理定理17.10可知邊數(shù)可知邊數(shù)10應(yīng)滿足應(yīng)滿足 10(3/(3-2)(5-2) = 9 這是個(gè)矛盾，所以這是個(gè)矛盾，所以K5不是平面圖。不是平面圖。 q若若K3,3是平面圖，由于是平面圖，由于K3,3中最短圈的長度為中最短圈的長度為l4，于是邊數(shù)于是邊數(shù)9應(yīng)滿足應(yīng)滿足 9 (4/(4-2)(6-2) = 8 這又是矛盾的，所以這又是矛盾的，所以K3,3也不是平面圖。也不是平面圖。 定理定理8.118.11 設(shè)設(shè)G是有是有k(k2)個(gè)連通分支的平面圖，各面的次數(shù)個(gè)連通分支的平面圖，各面的次數(shù)至少

16、為至少為l(l3)，則邊數(shù)則邊數(shù)m與頂點(diǎn)數(shù)與頂點(diǎn)數(shù)n應(yīng)有如下關(guān)系：應(yīng)有如下關(guān)系： (1)2lmnkl定理定理8.128.12 設(shè)設(shè)G為為n(n 3)階階m條邊的簡單平面圖，則條邊的簡單平面圖，則m 3n 6。 設(shè)設(shè)G有有k(k 1)個(gè)連通分支，個(gè)連通分支，q 若若G為樹或森林，當(dāng)為樹或森林，當(dāng)n 3時(shí)，時(shí)，m=n-k 3n 6為真。為真。q 若若G不是樹也不是森林，則不是樹也不是森林，則G中必含圈，又因?yàn)橹斜睾?，又因?yàn)镚是簡單圖，是簡單圖，所以，每個(gè)面至少由所以，每個(gè)面至少由l（l 3）條邊圍成，又在條邊圍成，又在l=3達(dá)到最大值達(dá)到最大值，由定理，由定理8.11可知可知證明證明2(1)(1

17、)(1)3(2)3622lmnknknnll定理定理8.138.13 設(shè)設(shè)G為為n(n 3)階階m條邊的極大平面圖，則條邊的極大平面圖，則m=3n 6。證明證明 由于極大平面圖是連通圖，由歐拉公式得由于極大平面圖是連通圖，由歐拉公式得: r=2+m-n (8.4) 又因?yàn)橛忠驗(yàn)镚是極大平面圖，由定理是極大平面圖，由定理17.7的必要性可知，的必要性可知，G的每個(gè)的每個(gè)面的次數(shù)均為面的次數(shù)均為3，所以：，所以： 將將(8.4)代入代入(8.5)，整理后得，整理后得 m = 3n-6。12deg()3(8.5)riimRr二、一個(gè)意義重大的定理二、一個(gè)意義重大的定理 定理定理8.148.14 設(shè)設(shè)

18、G為簡單平面圖，則為簡單平面圖，則G的最小度的最小度 (G) 5。q 若階數(shù)若階數(shù) n 6，結(jié)論顯然成立。結(jié)論顯然成立。q 若階數(shù)若階數(shù)n 7時(shí)，用反證法。時(shí)，用反證法。 假設(shè)假設(shè) (G) 6，由握手定理可知：由握手定理可知：證明證明12( )6niimd vn因而因而m 3n，這與定理這與定理8.12矛盾。矛盾。所以，假設(shè)不成立，即所以，假設(shè)不成立，即G的最小度的最小度 (G) 5。q本定理在圖著色理論中占重要地位。本定理在圖著色理論中占重要地位。說說明明定理定理8.78.7 設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖為極大平面圖當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G的每個(gè)

19、面的次數(shù)均為的每個(gè)面的次數(shù)均為3。（僅證。（僅證充分性充分性）由定理由定理17.4可知，可知，證證明明12( ) 3(8.6)niimd vr又因?yàn)橛忠驗(yàn)镚是連通的，由歐拉公式可知是連通的，由歐拉公式可知2(8.7)rmn將將(8.7)代入代入(8.6)，經(jīng)過整理得，經(jīng)過整理得m=3n-6。 (8.8)若若G不是極大平面圖，則不是極大平面圖，則G中一定存在不相鄰得頂點(diǎn)中一定存在不相鄰得頂點(diǎn)u,v，使得使得G=G (u,v)還是簡單平面圖，而還是簡單平面圖，而G的邊數(shù)的邊數(shù)m=m+1，n=n。由由(8.8)可知，可知， m3n-6 ，這與定理這與定理8.2矛盾。矛盾。所以，所以，G為極大平面圖。

20、為極大平面圖。小節(jié)結(jié)束小節(jié)結(jié)束1、 插入插入2度頂點(diǎn)和消去度頂點(diǎn)和消去2度頂點(diǎn)度頂點(diǎn)定義定義8.5 8.5 q 設(shè)設(shè)e=(u,v)為圖為圖G的一條邊，在的一條邊，在G中刪除中刪除e，增加新的頂點(diǎn)增加新的頂點(diǎn)w，使使u、v均與均與w相鄰，稱為在相鄰，稱為在G中中插入插入2度頂點(diǎn)度頂點(diǎn)w。q 設(shè)設(shè)w為為G中一個(gè)中一個(gè)2度頂點(diǎn)，度頂點(diǎn)，w與與u、v相鄰，刪除相鄰，刪除w，增加新邊增加新邊(u,v)，稱為在稱為在G中中消去消去2度頂點(diǎn)度頂點(diǎn)w。8.3 8.3 平面圖的判斷平面圖的判斷2、圖之間的同胚、圖之間的同胚定義定義8.68.6 若兩個(gè)圖若兩個(gè)圖G1與與G2同構(gòu)，或通過反復(fù)插入或消去同構(gòu)，或通過反

21、復(fù)插入或消去2度頂點(diǎn)后是同構(gòu)的，則稱度頂點(diǎn)后是同構(gòu)的，則稱G1與與G2是是同胚同胚的。的。上面兩個(gè)圖分別與上面兩個(gè)圖分別與K3,3, K5同胚同胚 。二、兩個(gè)判斷定理二、兩個(gè)判斷定理 定理定理8.158.15(庫拉圖斯基定理庫拉圖斯基定理1) 圖圖G是平面圖當(dāng)且僅當(dāng)是平面圖當(dāng)且僅當(dāng)G中既不含中既不含與與K5同胚子圖，也不含與同胚子圖，也不含與K3,3同胚子圖。同胚子圖。 8.4 8.4 平面圖的對(duì)偶圖平面圖的對(duì)偶圖一、對(duì)偶圖的定義一、對(duì)偶圖的定義定義定義8.78.7 設(shè)設(shè)G是平面圖，構(gòu)造是平面圖，構(gòu)造G的對(duì)偶圖的對(duì)偶圖G*如下：如下：q 在在G的面的面Ri中放置中放置G*的頂點(diǎn)的頂點(diǎn)vi* 。

22、q 設(shè)設(shè)e為為G的任意一條邊，的任意一條邊，若若e在在G的面的面Ri與與Rj的公共邊界上，做的公共邊界上，做G*的邊的邊e*與與e相交，相交，且且e*關(guān)聯(lián)關(guān)聯(lián)G*的位于的位于Ri與與Rj中的頂點(diǎn)中的頂點(diǎn)vi*與與vj*，即即e*=(vi*,vj*)，e*不與其它任何邊相交。不與其它任何邊相交。若若e為為G中的橋且在面中的橋且在面Ri的邊界上，則的邊界上，則e*是以是以Ri中中G*的頂點(diǎn)的頂點(diǎn)vi*為端點(diǎn)的環(huán)，即為端點(diǎn)的環(huán)，即e*=(vi*,vi*)。實(shí)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖。實(shí)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖。從定義不難看出從定義不難看出G的對(duì)偶圖的對(duì)偶圖G*有以下性質(zhì)：有以下性

23、質(zhì)：q G*是平面圖。是平面圖。q G*是連通圖。是連通圖。q 若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為橋，若為橋，若e為橋，為橋，則則G*中與中與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為環(huán)。為環(huán)。q 在多數(shù)情況下，在多數(shù)情況下，G*為多重圖（含平行邊的圖）。為多重圖（含平行邊的圖）。q 同構(gòu)的平面圖的對(duì)偶圖不一定是同構(gòu)的。同構(gòu)的平面圖的對(duì)偶圖不一定是同構(gòu)的。二、平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系。二、平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系。定理定理8.168.16 設(shè)設(shè)G*是連通平面圖是連通平面圖G的對(duì)偶圖，的對(duì)偶圖，n*、m*、r*和和n、 m、r分別為分別為G*和

24、和G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則（1）n*= r（2）m*=m（3）r*=nq (1)、(2)由由G*的構(gòu)造可知是顯然的。的構(gòu)造可知是顯然的。 q (3)由于由于G與與G*都連通，因而滿足歐拉公式都連通，因而滿足歐拉公式: n-m+r = 2 n*-m*+r* = 2 由由(1)、(2)可知，可知， r* = 2+m*-n* = 2+m-r = n證證明明定理定理8.178.17 設(shè)設(shè)G*是具有是具有k（k 2）個(gè)連通分支的平面圖個(gè)連通分支的平面圖G的對(duì)的對(duì)偶圖，偶圖， n*, m*, r*, n, m, r分別為分別為G*和和G的頂點(diǎn)數(shù)、邊數(shù)和的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，面數(shù)，

25、（1）n*= r（2）m*=m（3）r*=n k+1三、自對(duì)偶圖三、自對(duì)偶圖定義定義8.88.8 設(shè)設(shè)G*是平面圖是平面圖G的對(duì)偶圖，若的對(duì)偶圖，若G* G，則稱則稱G為自對(duì)偶為自對(duì)偶圖。圖。q 在在n 1(n 4)邊形邊形Cn 1內(nèi)放置內(nèi)放置1個(gè)頂點(diǎn)，使這個(gè)頂點(diǎn)與個(gè)頂點(diǎn)，使這個(gè)頂點(diǎn)與Cn 1上的上的所有的頂點(diǎn)均相鄰，所得所有的頂點(diǎn)均相鄰，所得n階簡單圖稱為階簡單圖稱為n階輪圖階輪圖。記為。記為Wn。 q n為奇數(shù)的輪圖稱為為奇數(shù)的輪圖稱為奇階輪圖奇階輪圖。q n為偶數(shù)的輪圖稱為為偶數(shù)的輪圖稱為偶階輪圖偶階輪圖。q 輪圖都是自對(duì)偶圖。輪圖都是自對(duì)偶圖。小節(jié)結(jié)束小節(jié)結(jié)束8.5 8.5 圖中頂點(diǎn)的

26、著色圖中頂點(diǎn)的著色規(guī)定：規(guī)定：點(diǎn)著色都是對(duì)無環(huán)無向圖進(jìn)行的。點(diǎn)著色都是對(duì)無環(huán)無向圖進(jìn)行的。一、關(guān)于頂點(diǎn)著色的基本概念一、關(guān)于頂點(diǎn)著色的基本概念定義定義8.98.9 （1）圖）圖G的一種著色的一種著色對(duì)無環(huán)圖對(duì)無環(huán)圖G的每個(gè)頂點(diǎn)涂上一種顏的每個(gè)頂點(diǎn)涂上一種顏 色，使相鄰頂點(diǎn)涂不同的顏色。色，使相鄰頂點(diǎn)涂不同的顏色。（2）對(duì)）對(duì)G進(jìn)行進(jìn)行k著色（著色（G是是k-可著色的）可著色的）能用能用k種顏色給種顏色給G 的頂點(diǎn)著色。的頂點(diǎn)著色。（3）G的色數(shù)的色數(shù) (G)=kG是是k-可著色的，但不是可著色的，但不是(k 1)-可著可著 色的。色的。二、關(guān)于頂點(diǎn)著色的幾個(gè)簡單結(jié)果二、關(guān)于頂點(diǎn)著色的幾個(gè)簡單結(jié)

27、果定理定理8.188.18 (G)=1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為零圖。為零圖。定理定理8.198.19 (Kn)=n。 定理定理8.208.20 奇階輪圖的色數(shù)均為奇階輪圖的色數(shù)均為3，偶階輪圖的色數(shù)為偶階輪圖的色數(shù)為4。定理定理8.218.21 設(shè)設(shè)G中至少含有一條邊，則中至少含有一條邊，則 (G)=2當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G為二部圖為二部圖。三、色數(shù)的上界三、色數(shù)的上界定理定理8.228.22 對(duì)于任意無向圖對(duì)于任意無向圖G，均有均有 (G) (G)+1。q n=1時(shí)，結(jié)論成立。時(shí)，結(jié)論成立。q 設(shè)設(shè)n=k(k1)時(shí)結(jié)論成立，則當(dāng)時(shí)結(jié)論成立，則當(dāng)n=k+1時(shí)，時(shí)， 設(shè)設(shè)v為為G中任一個(gè)頂點(diǎn)，令中任一個(gè)

28、頂點(diǎn)，令G=G-v，則則G的階數(shù)為的階數(shù)為k，由假設(shè)由假設(shè)可知可知 (G) (G)+1 (G)+1。 當(dāng)將當(dāng)將G還原成還原成G時(shí)，由于時(shí)，由于v至多與至多與G中中(G)個(gè)頂點(diǎn)相鄰，而在個(gè)頂點(diǎn)相鄰，而在G的點(diǎn)著色中，的點(diǎn)著色中，(G)個(gè)頂點(diǎn)至多用了個(gè)頂點(diǎn)至多用了(G)種顏色，于是在種顏色，于是在(G)+1種顏色中至少存在一種顏色給種顏色中至少存在一種顏色給v涂色，使涂色，使v與相鄰頂點(diǎn)與相鄰頂點(diǎn)涂不同顏色。涂不同顏色。 證證明明提示：對(duì)提示：對(duì)G的階數(shù)的階數(shù)n作歸納法。作歸納法。例例 求下面各圖的色數(shù)。求下面各圖的色數(shù)。 定理定理8.23 8.23 ( (布魯克斯定理布魯克斯定理) 若連通無向圖若連通無向圖G不是不是Kn(n 3)，也不是也不是奇數(shù)階的圈，則奇數(shù)階的圈，則 (G) (G)。q 因?yàn)橐驗(yàn)?1)為為二部圖，由定理二部圖，由定理8.21可知，可知， (G) =2。q (