平面圖及圖的著色

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

2、平面。q G的平面嵌入的平面嵌入畫出的無邊相交的平面圖。畫出的無邊相交的平面圖。q 非平面圖非平面圖無平面嵌入的圖。無平面嵌入的圖。（2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。2、 幾點說明及一些簡單結論幾點說明及一些簡單結論q 一般所談平面圖不一定是指平面嵌入，但討論某些性質時，一般所談平面圖不一定是指平面嵌入，但討論某些性質時，一定是指平面嵌入。一定是指平面嵌入。q K5和和K3,3都不是平面圖。都不是平面圖。q 定理定理8.1 8.1 設設GG，若若G為平面圖，則為平面圖，則G 也是平面圖。也是平面圖。q 定理定理8.2 8.2 設設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ù)（針對平面圖的平面嵌入）二、平面圖的面與次數(shù)（針對平面圖的平面嵌入）1、 定義定義定義定義8.28.2 設設G是平面圖，是平面圖，q G的面的面由由G的邊將的邊將G所在的平面劃分成的每一個區(qū)域。所在的平面劃分成的每一個區(qū)域。q 無限面（外部面）無

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

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

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

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

8、面的次數(shù)均為3。q由于由于n 3, 又又G必為簡單平面圖，可知，必為簡單平面圖，可知，G每個面的次數(shù)均每個面的次數(shù)均 3。q因為因為G為平面圖，又為極大平面圖?？勺C為平面圖，又為極大平面圖?？勺CG不可能存在次數(shù)不可能存在次數(shù)3的面。的面。證證明明思思路路假設存在面假設存在面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的的每個面為每個面為3條邊所圍，也就是各面次數(shù)均為條邊所圍，也就是各面次數(shù)均為3。sS-1 只有右邊的圖為極大平面圖。只有右邊的圖為極大平面圖。 因為只有該圖每個面的次數(shù)都為因為只有該圖每個面的次數(shù)都為3。 四、極小非平面圖四、極小非平面圖定義定義8.48.4 若在非平面圖若在非平面圖G中

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、和G的頂點數(shù)、邊數(shù)和面數(shù)，則的頂點數(shù)、邊數(shù)和面數(shù)，則（1）n*= r（2）m*=m（3）r*=nq (1)、(2)由由G*的構造可知是顯然的。的構造可知是顯然的。 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 設設G*是具有是具有k（k 2）個連通分支的平面圖個連通分支的平面圖G的對的對偶圖，偶圖， n*, m*, r*, n, m, r分別為分別為G*和和G的頂點數(shù)、邊數(shù)和的頂點數(shù)、邊數(shù)和面數(shù)，面數(shù)，

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

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

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

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