離散數(shù)學(xué)平面圖及圖的著色

1、第17章 平面圖及圖的著 色 離離 散散 數(shù)數(shù) 學(xué)學(xué) 江蘇科技大學(xué)本科生必修課程江蘇科技大學(xué)本科生必修課程 計算機系計算機系 周塔周塔 本章說明本章說明 q本章的主要內(nèi)容本章的主要內(nèi)容 平面圖的基本概念平面圖的基本概念 歐拉公式歐拉公式 平面圖的判斷平面圖的判斷 平面圖的對偶圖平面圖的對偶圖 頂點著色及點色數(shù)頂點著色及點色數(shù) 地圖的著色與平面圖的點著色地圖的著色與平面圖的點著色 邊著色及邊色數(shù)邊著色及邊色數(shù) 特別說明：特別說明： 本章所涉及到的圖均指無向圖。本章所涉及到的圖均指無向圖。 17.1 平面圖的基本概念平面圖的基本概念 一、關(guān)于平面圖的一些基本概念一、關(guān)于平面圖的一些基本概念 1、

2、平面圖的定義平面圖的定義 定義定義17.117.1 q 如果圖如果圖G能以這樣的方式畫在曲面能以這樣的方式畫在曲面S上，即除頂點處外無上，即除頂點處外無 邊相交，稱圖邊相交，稱圖G G為平面圖。為平面圖。 q G的平面嵌入的平面嵌入畫出的無邊相交的平面圖。畫出的無邊相交的平面圖。 （2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。 2、 幾點說明及一些簡單結(jié)論幾點說明及一些簡單結(jié)論 q 一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時，一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時， 一定是指平面嵌入。一定是指平面嵌入。 q很顯然：很顯然：K5和

3、和K3,3都不是平面圖。都不是平面圖。見見P181 q 定理定理17.1 17.1 設(shè)設(shè)GG，若若G為平面圖，則為平面圖，則G 也是平面圖。也是平面圖。 q 定理定理17.2 17.2 設(shè)設(shè)GG，若若G 為非平面圖，則為非平面圖，則G也是非平面圖。也是非平面圖。 q 推論推論 Kn(n 5)和和K3,n(n 3)都是非平面圖。都是非平面圖。 q 定理定理17.3 17.3 若若G為平面圖，則在為平面圖，則在G中加平行邊或環(huán)所得圖還是中加平行邊或環(huán)所得圖還是 平面圖。平面圖。 即平行邊和環(huán)不影響圖的平面性。即平行邊和環(huán)不影響圖的平面性。 二、平面圖的面與次數(shù)（針對平面圖的平面嵌入而言）二、平面圖

4、的面與次數(shù)（針對平面圖的平面嵌入而言） 1、 定義定義 定義定義17.217.2 設(shè)設(shè)G是平面圖，是平面圖， q G的面的面由由G的邊將的邊將G所在的平面劃分成的每一個區(qū)域。所在的平面劃分成的每一個區(qū)域。 q 無限面（外部面）無限面（外部面）面積無限的面，記作面積無限的面，記作R0。 q 有限面（內(nèi)部面）有限面（內(nèi)部面）面積有限的面面積有限的面 ，記作，記作R1, R2, , Rk。 q 面面Ri的邊界的邊界包圍面包圍面Ri的所有邊組成的回路組。的所有邊組成的回路組。 q 面面Ri的次數(shù)的次數(shù)Ri邊界的長度，記作邊界的長度，記作deg(Ri)。 2、幾點說明、幾點說明 q 若平面圖若平面圖G有

5、有k個面，可籠統(tǒng)地用個面，可籠統(tǒng)地用R1, R2, , Rk表示，不需表示，不需 要指出外部面。要指出外部面。 q 回路組是指：邊界可能是初級回路（圈），可能是簡單回回路組是指：邊界可能是初級回路（圈），可能是簡單回 路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路 之并。之并。 平面圖有平面圖有4個面，個面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1 R2 R3 R0 定理定理17.417.4 平面圖平面圖G中所有面的次數(shù)之和等于邊數(shù)中所有面的次數(shù)之和等于邊數(shù)m的兩倍，即的兩倍，即 本定理中

6、所說平面圖是指平面嵌入。本定理中所說平面圖是指平面嵌入。 eE(G)， 當(dāng)當(dāng)e為面為面Ri和和Rj(ij)的公共邊界上的邊時，在計算的公共邊界上的邊時，在計算Ri和和Rj的次的次 數(shù)時，數(shù)時，e各提供各提供1。 當(dāng)當(dāng)e只在某一個面的邊界上出現(xiàn)時，則在計算該面的次數(shù)時只在某一個面的邊界上出現(xiàn)時，則在計算該面的次數(shù)時 ，e提供提供2。 于是每條邊在計算總次數(shù)時，都提供于是每條邊在計算總次數(shù)時，都提供2，因而，因而deg(Ri)=2m。 1 deg()2 r i i RmrG 其中 為 的面數(shù) 證證 明明 三、極大平面圖三、極大平面圖 1、 定義定義 定義定義17.317.3 若在簡單平面圖若在簡單

7、平面圖G中的任意兩個不相鄰的頂點之中的任意兩個不相鄰的頂點之 間加一條新邊所得圖為非平面圖，則稱間加一條新邊所得圖為非平面圖，則稱G為為極大平面圖極大平面圖。 注意：注意：若簡單平面圖若簡單平面圖G中已中已無不相鄰頂點無不相鄰頂點，G顯然是極大平顯然是極大平 面圖，如面圖，如K1（平凡圖）平凡圖）, K2, K3, K4都是極大平面圖。都是極大平面圖。 2、極大平面圖的主要性質(zhì)、極大平面圖的主要性質(zhì) 定理定理17.517.5 極大平面圖是連通的。極大平面圖是連通的。(根據(jù)注意！根據(jù)注意！) 定理定理17.617.6 n(n 3)階極大平面圖中不可能有割點和橋。階極大平面圖中不可能有割點和橋。

8、定理定理17.717.7 設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖為極大平面圖 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G的每個面的次數(shù)均為的每個面的次數(shù)均為3。 四、極小非平面圖四、極小非平面圖 定義定義17.417.4 若在非平面圖若在非平面圖G中任意刪除一條邊，所得圖中任意刪除一條邊，所得圖G為平面為平面 圖，則稱圖，則稱G為極小非平面圖。為極小非平面圖。 由定義不難看出：由定義不難看出： q K5, K3,3都是極小非平面圖。都是極小非平面圖。 q 極小非平面圖必為簡單圖。極小非平面圖必為簡單圖。 例如：例如：以下各圖均為極小非平面圖。以下各圖均為極小非平面圖。 小節(jié)結(jié)

9、束小節(jié)結(jié)束 17.2 17.2 歐拉公式歐拉公式 一、歐拉公式相關(guān)定理一、歐拉公式相關(guān)定理 1、 歐拉公式歐拉公式 定理定理17.8 17.8 對于任意的連通的平面圖對于任意的連通的平面圖G，有有 n-m+r=2 其中，其中，n、m、r分別為分別為G的頂點數(shù)、邊數(shù)和面數(shù)。的頂點數(shù)、邊數(shù)和面數(shù)。 定理定理17.9 17.9 對于具有對于具有k(k2)個連通分支的平面圖個連通分支的平面圖G，有有 n-m+r = k+1 其中其中n，m，r分別為分別為G的頂點數(shù)，邊數(shù)和面數(shù)。的頂點數(shù)，邊數(shù)和面數(shù)。 證明證明 設(shè)設(shè)G的連通分支分別為的連通分支分別為G1、G2、Gk，并設(shè)并設(shè)Gi的頂點數(shù)、邊的頂點數(shù)、邊

10、 數(shù)、面數(shù)分別為數(shù)、面數(shù)分別為ni、mi、ri、i=1，2，k。 由歐拉公式可知由歐拉公式可知: ni-mi+ri = 2，i=1，2，k (17.1) 易知，易知， 11 kk ii ii mmnn ， 由于每個由于每個Gi 有一個外部面，而有一個外部面，而G只有一個外部面，所以只有一個外部面，所以G的面數(shù)的面數(shù) 1 1 k i i rrk 于是，于是，對對(17.1)的兩邊同時求和得的兩邊同時求和得 1111 2()1 kkkk iiiiii iiii knmrnmrnmrk 經(jīng)整理得經(jīng)整理得 n-m+r = k+1。 2、 與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理 定理定理17.1017

11、.10 設(shè)設(shè)G為連通的平面圖，且每個面的次數(shù)至少為為連通的平面圖，且每個面的次數(shù)至少為 l(l=3)，則則 G的邊數(shù)與頂點數(shù)有如下關(guān)系：的邊數(shù)與頂點數(shù)有如下關(guān)系： 由定理由定理17.4（面的次數(shù)之和等于邊數(shù)的（面的次數(shù)之和等于邊數(shù)的2倍）及歐拉公式得倍）及歐拉公式得 (2) 2 l mn l 證明證明 1 2deg()(2) r i i mRl rlmn 解得解得 (2) 2 l mn l 推論推論 K5, K3,3不是平面圖。不是平面圖。 證明證明 q若若K5是平面圖，由于是平面圖，由于K5中無環(huán)和平行邊，所以每個面的次數(shù)中無環(huán)和平行邊，所以每個面的次數(shù) 均大于或等于均大于或等于l3，由由定

12、理定理17.10可知邊數(shù)可知邊數(shù)10應(yīng)滿足應(yīng)滿足 10(3/(3-2)(5-2) = 9 這是個矛盾，所以這是個矛盾，所以K5不是平面圖。不是平面圖。 q若若K3,3是平面圖，由于是平面圖，由于K3,3中最短圈的長度為中最短圈的長度為l4，于是邊數(shù)于是邊數(shù)9 應(yīng)滿足應(yīng)滿足 9 (4/(4-2)(6-2) = 8 這又是矛盾的，所以這又是矛盾的，所以K3,3也不是平面圖。也不是平面圖。 定理定理17.1117.11 設(shè)設(shè)G是有是有k(k2)個連通分支的平面圖，各面的次數(shù)個連通分支的平面圖，各面的次數(shù) 至少為至少為l(l3)，則邊數(shù)則邊數(shù)m與頂點數(shù)與頂點數(shù)n應(yīng)有如下關(guān)系：應(yīng)有如下關(guān)系： (1) 2

13、 l mnk l 定理定理17.1217.12 設(shè)設(shè)G為為n(n 3)階階m條邊的簡單平面圖，則條邊的簡單平面圖，則m 3n 6。 設(shè)設(shè)G有有k(k 1)個連通分支，個連通分支， q 若若G為樹或森林，當(dāng)為樹或森林，當(dāng)n 3時，時，m=n-k 3n 6為真。為真。 q 若若G不是樹也不是森林，則不是樹也不是森林，則G中必含圈，又因為中必含圈，又因為G是簡單圖，是簡單圖， 所以，每個面至少由所以，每個面至少由l（l 3）條邊圍成，又在條邊圍成，又在l=3達到最大值達到最大值 ，由定理，由定理17.11可知可知 證明證明 2 (1)(1)(1)3(2)36 22 l mnknknn ll 定理定理

14、17.1317.13 設(shè)設(shè)G為為n(n 3)階階m條邊的極大平面圖，則條邊的極大平面圖，則m=3n 6。 證明證明 由于極大平面圖是連通圖，由歐拉公式得由于極大平面圖是連通圖，由歐拉公式得: r=2+m-n (17.4) 又因為又因為G是極大平面圖，由定理是極大平面圖，由定理17.7的必要性可知，的必要性可知，G的每個的每個 面的次數(shù)均為面的次數(shù)均為3，所以：，所以： 將將(17.4)代入代入(17.5)，整理后得，整理后得 m = 3n-6。 1 2deg()3(17.5) r i i mRr 二、二、一個意義重大的定理一個意義重大的定理 定理定理17.1417.14 設(shè)設(shè)G為簡單平面圖，則

15、為簡單平面圖，則G的最小度的最小度 (G) 5。 q 若階數(shù)若階數(shù) n 6，結(jié)論顯然成立。結(jié)論顯然成立。 q 若階數(shù)若階數(shù)n 7時，用反證法。時，用反證法。 假設(shè)假設(shè) (G) 6，由握手定理可知：由握手定理可知： 證明證明 1 2( )6 n i i md vn 因而因而m 3n，這與定理這與定理17.12(m3n6)矛盾。矛盾。 所以，假設(shè)不成立，即所以，假設(shè)不成立，即G的最小度的最小度 (G) 5。 q本定理在圖著色理論中占重要地位。本定理在圖著色理論中占重要地位。 說說 明明 定理定理17.717.7 設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面為極大平

16、面 圖當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為的每個面的次數(shù)均為3。 小節(jié)結(jié)束小節(jié)結(jié)束 一、為判斷定理做準(zhǔn)備一、為判斷定理做準(zhǔn)備 1、 插入插入2度頂點和消去度頂點和消去2度頂點度頂點 定義定義17.5 17.5 q 設(shè)設(shè)e=(u,v)為圖為圖G的一條邊，在的一條邊，在G中刪除中刪除e，增加新的頂點增加新的頂點w， 使使u、v均與均與w相鄰，稱為在相鄰，稱為在G中中插入插入2度頂點度頂點w。 q 設(shè)設(shè)w為為G中一個中一個2度頂點，度頂點，w與與u、v相鄰，刪除相鄰，刪除w，增加新邊增加新邊 (u,v)，稱為在稱為在G中中消去消去2度頂點度頂點w。 17.3 17.3 平面圖的判斷平面圖的判斷 圖

17、的同構(gòu)圖的同構(gòu) 2、圖之間的同胚、圖之間的同胚 定義定義17.617.6 若兩個圖若兩個圖G1與與G2同構(gòu)，或通過反復(fù)插入或消去同構(gòu)，或通過反復(fù)插入或消去2 度頂點后是同構(gòu)的，則稱度頂點后是同構(gòu)的，則稱G1與與G2是是同胚同胚的。的。 上面兩個圖分別與上面兩個圖分別與K3,3, K5同胚同胚 。 17.4 17.4 平面圖的對偶圖平面圖的對偶圖 一、對偶圖的定義一、對偶圖的定義 定義定義17.717.7 設(shè)設(shè)G是某平面圖的某個平面嵌入，構(gòu)造是某平面圖的某個平面嵌入，構(gòu)造G的對偶圖的對偶圖 G*如下：如下： q 在在G的面的面Ri中放置中放置G*的頂點的頂點vi* 。 q 設(shè)設(shè)e為為G的任意一條

18、邊，的任意一條邊， 若若e在在G的面的面Ri與與Rj的公共邊界上，做的公共邊界上，做G*的邊的邊e*與與e相交，相交， 且且e*關(guān)聯(lián)關(guā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*有以下性質(zhì)：有以下性質(zhì)： q G*是平面圖，而且是平面嵌入。是平面圖，而且是平面嵌入。 q G*是連通圖。是連通圖。 q 若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對應(yīng)的邊對應(yīng)的邊e*為橋，若為橋，若e為橋，為橋， 則則G*中與中與e對應(yīng)的邊對應(yīng)的邊e*為環(huán)。為環(huán)。 q 在多數(shù)情況下，在多數(shù)情況下，G*為多重圖（含平行邊的圖）。為多重圖（含平行邊的圖）。 q 同構(gòu)的平面圖（平面嵌入）的對偶圖不一定是同構(gòu)