離散數學第十七章平面圖

1、1第十七章第十七章 平面圖平面圖本章的主要內容本章的主要內容l 平面圖的基本概念平面圖的基本概念l 歐拉公式歐拉公式l 平面圖的判斷平面圖的判斷l(xiāng) 平面圖的對偶圖平面圖的對偶圖2引言引言許多實際問題可以抽象為這樣的模式：在一些表示客體的結許多實際問題可以抽象為這樣的模式：在一些表示客體的結點之間點之間“布線布線”、“建通道建通道”，以建立它們之間的某些聯，以建立它們之間的某些聯系，要求這些系，要求這些“線線”、“通道通道”在一個平面上而又不相互在一個平面上而又不相互交疊。這正是本章要討論的圖論問題。交疊。這正是本章要討論的圖論問題。例如，要在三個工作點例如，要在三個工作點a,b,c和三個原料庫

2、和三個原料庫l,m,n之間建立之間建立各工作點到原料庫的傳輸線，問是否可能使這些線路互不各工作點到原料庫的傳輸線，問是否可能使這些線路互不相交？如果用結點表示工作站，用邊表示傳輸線，那么上相交？如果用結點表示工作站，用邊表示傳輸線，那么上述問題便可描述為：述問題便可描述為：k3,3是否可以在一個平面上圖示出來，是否可以在一個平面上圖示出來，使圖中各邊除端點外均不相交？另外，印刷電路板上的布使圖中各邊除端點外均不相交？另外，印刷電路板上的布線與交通道路的設計等都是此類問題。為了深入討論這個線與交通道路的設計等都是此類問題。為了深入討論這個問題，需要引入平面圖的概念。問題，需要引入平面圖的概念。3

3、在圖中，在圖中，(2)是是(1) 的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.17.1 平面圖平面圖的基本概念的基本概念定義定義17.1 (1) g可嵌入曲面可嵌入曲面s若能將若能將g除頂點外無邊相交地畫在除頂點外無邊相交地畫在s上上(2) g是是可平面圖可平面圖或或平面圖平面圖g可嵌入平面可嵌入平面 (3) 平面嵌入平面嵌入畫出的無邊相交的平面圖畫出的無邊相交的平面圖(4) 非平面圖非平面圖無平面嵌入的無向圖無平面嵌入的無向圖 (1) (2) (3) (4)4幾點說明及一些簡單結論幾點說明及一些簡單結論一般所談平面圖不一定是指平面嵌入，上圖中一般所談平面圖不一定是指平面嵌入

4、，上圖中4個圖都是平個圖都是平面圖，但討論某些性質時，一定是指平面嵌入面圖，但討論某些性質時，一定是指平面嵌入. 結論：結論： (1) k5, k3,3都不是平面圖（待證）都不是平面圖（待證）(2) 設設gg，若，若g為平面圖，則為平面圖，則g 也是平面圖（定理也是平面圖（定理17.1）(3) 設設gg，若，若g 為非平面圖，則為非平面圖，則g也是非平面圖（定理也是非平面圖（定理17.2），由此可知，），由此可知，kn(n 6)，k3,n(n 4) 都是非平面圖都是非平面圖. (4) 平行邊與環(huán)不影響平面性平行邊與環(huán)不影響平面性. 5平面圖平面圖(平面嵌入平面嵌入)的面與次數的面與次數定義定義

5、17.2 (1) g的的面面由由g的平面嵌入的邊將平面化分成的區(qū)域的平面嵌入的邊將平面化分成的區(qū)域(2) 無限面無限面或或外部面外部面（可用（可用r0表示）表示）面積無限的面面積無限的面(3) 有限面有限面或或內部面內部面（可用（可用r1, r2, , rk等表示）等表示）面積面積 有限的面有限的面 (4) 面面 ri 的邊界的邊界包圍包圍ri的回路組的回路組(5) 面面 ri 的次數的次數ri邊界的長度，用邊界的長度，用deg(ri)表示表示 6定理定理17.4 平面圖各面次數之和等于邊數的兩倍平面圖各面次數之和等于邊數的兩倍. 幾點說明幾點說明l 若平面圖若平面圖g有有k個面，可籠統(tǒng)地用個

6、面，可籠統(tǒng)地用r1, r2, , rk表示，不需表示，不需要指出外部面要指出外部面.l 定義定義17.2(4) 中回路組是指：邊界可能是初級回路中回路組是指：邊界可能是初級回路(圈圈)，可，可能是簡單回路，也可能是復雜回路能是簡單回路，也可能是復雜回路. 特別地，還可能是非特別地，還可能是非連通的回路之并連通的回路之并. 平面圖有平面圖有4個面，個面，deg(r1)=1, deg(r2)=3, deg(r3)=2, deg(r0)=8. 請寫各面的邊界請寫各面的邊界. 7極大平面圖極大平面圖定義定義17.3 若在簡單平面圖若在簡單平面圖g中的任意兩個不相鄰的頂點之間中的任意兩個不相鄰的頂點之間

7、加一條新邊所得圖為非平面圖，則稱加一條新邊所得圖為非平面圖，則稱g為為極大平面圖極大平面圖.注意：若簡單平面圖注意：若簡單平面圖g中已無不相鄰頂點，中已無不相鄰頂點，g顯然是極大平顯然是極大平面圖，如面圖，如k1(平凡圖平凡圖), k2, k3, k4都是極大平面圖都是極大平面圖.極大平面圖的主要性質極大平面圖的主要性質定理定理17.5 極大平面圖是連通的極大平面圖是連通的. 證明線索：否則，加新邊不破壞平面性證明線索：否則，加新邊不破壞平面性定理定理17.6 n（n 3）階極大平面圖中不可能有割點和橋）階極大平面圖中不可能有割點和橋. 證明線索：由定理證明線索：由定理17.5及及n 3可知，

8、可知，g中若有橋，則一定有中若有橋，則一定有割點，因而只需證無割點即可割點，因而只需證無割點即可. 方法還是反證法方法還是反證法.8證明線索：證明線索：(1) 由于由于n 3, 又又g必為簡單必為簡單平面圖可知，平面圖可知，g每個面的每個面的次數均次數均 3.(2) 因為因為g為平面圖，又為極為平面圖，又為極大平面圖大平面圖. 可證可證g不可能不可能存在次數存在次數3的面的面. 就給出的圖討論即可就給出的圖討論即可. 極大平面圖的性質極大平面圖的性質定理定理17.7 設設g為為n（n 3）階極大平面圖，則）階極大平面圖，則g的每個面的的每個面的次數均為次數均為3. 9定理定理17.7中的條件也

9、是極大平面圖的充分條件中的條件也是極大平面圖的充分條件. 定理定理17.7 設設g為為n (n 3) 階平面圖，且每個面的次數均為階平面圖，且每個面的次數均為3，則則g為極大平面圖為極大平面圖.定理的應用定理的應用上圖中，只有上圖中，只有(3)為極大平面圖為極大平面圖 (1) (2) (3) 10極小非平面圖極小非平面圖定義定義17.4 若在非平面圖若在非平面圖g中任意刪除一條邊，所得圖中任意刪除一條邊，所得圖g 為平為平面圖，則稱面圖，則稱g為為極小非平面圖極小非平面圖.由定義不難看出：由定義不難看出：(1) k5, k3,3都是極小非平面圖都是極小非平面圖(2) 極小非平面圖必為簡單圖極小

10、非平面圖必為簡單圖圖中所示各圖都是極小非平面圖圖中所示各圖都是極小非平面圖.11定理定理17.9 （歐拉公式的推廣）設（歐拉公式的推廣）設g是具有是具有k（k 2）個連通）個連通分支的平面圖，則分支的平面圖，則n m+r=k+1證明中對各連通分支用歐拉公式，并注意證明中對各連通分支用歐拉公式，并注意即可即可. kiikrr1)1(17.2 歐拉公式歐拉公式定理定理17.8 設設g為為n階階m條邊條邊r個面的連通平面圖，則個面的連通平面圖，則n m+r=2（此公式稱為（此公式稱為歐拉公式歐拉公式）證證 對邊數對邊數m做歸納法做歸納法m=0，g為平凡圖，結論為真為平凡圖，結論為真.設設m=k（k

11、1）結論為真，）結論為真，m=k+1時分情況討論時分情況討論.(1) g中無圈，則中無圈，則g為樹，刪除一片樹葉，用歸納假設為樹，刪除一片樹葉，用歸納假設.(2) 否則，在某一個圈上刪除一條邊，進行討論否則，在某一個圈上刪除一條邊，進行討論.12)2(2 nllm)2()deg(21nmlrlrmrii )2(2 nllm)1(2 knllm解得解得 定理定理17.11 在具有在具有k（k 2）個連通分支的平面圖中，）個連通分支的平面圖中，與歐拉公式有關的定理與歐拉公式有關的定理定理定理17.10 設設g為連通的平面圖，且為連通的平面圖，且deg(ri) l, l 3，則，則 證證 由定理由定

12、理17.4及及歐拉公式得歐拉公式得推論推論 k5, k3,3不是平面圖不是平面圖.13定理定理17.12 設設g為為n（n 3）階）階m條邊的簡單平面圖，則條邊的簡單平面圖，則m 3n 6. 證證 設設g有有k（k 1）個連通分支，若）個連通分支，若g為樹或森林，當為樹或森林，當n 3時，時，m 3n 6為真為真. 否則否則g中含圈，每個面至少由中含圈，每個面至少由l（l 3）條邊圍成）條邊圍成，又，又2212 lll定理定理17.13 設設g為為n（n 3）階）階m條邊的極大平面圖，則條邊的極大平面圖，則m=3n 6.證證 由定理由定理17.4, 歐拉公式及定理歐拉公式及定理17.7所證所證

13、. 定理定理17.14 設設g 為簡單平面圖，則為簡單平面圖，則 (g) 5. 證證 階數階數 n 6，結論為真，結論為真. 當當n 7 時，用反證法時，用反證法. 否則會推出否則會推出2m 6n m 3n，這與定理，這與定理17.12矛盾矛盾. 與歐拉公式有關的定理與歐拉公式有關的定理在在l=3達到最大值，由定理達到最大值，由定理17.11可知可知m 3n 6.1417.3 平面圖的判斷平面圖的判斷1. 插入插入2度頂點和消去度頂點和消去2度頂點度頂點定義定義17.5(1) 消去消去2度頂點度頂點v，見下圖中，由，見下圖中，由(1) 到到(2) (2) 插入插入2度頂點度頂點v，見下圖中，從

14、，見下圖中，從(2) 到到(1) . (1) (2) 152. 收縮邊收縮邊e，見下圖所示，見下圖所示.3. 圖之間的同胚圖之間的同胚定義定義17.6 若若g1 g2，或經過反復插入或消去，或經過反復插入或消去2度頂點后所度頂點后所得得g 1 g 2，則稱，則稱g1與與g2同胚同胚. 圖的同胚圖的同胚右邊兩個圖同胚右邊兩個圖同胚16平面圖判定定理平面圖判定定理定理定理17.15 g是平面圖是平面圖 g中不含與中不含與k5或或k3,3同胚的子圖同胚的子圖.定理定理17.16 g是平面圖是平面圖 g中無可收縮為中無可收縮為k5或或k3,3的子圖的子圖例例1 證明所示圖證明所示圖(1)與與(2)均為

15、非平面圖均為非平面圖. (1) (2)右圖右圖(1),(2)分別為分別為原圖原圖(1), (2)的子圖的子圖與與k3,3, k5同胚同胚. 子圖子圖 (1) (2) 1717.4 平面圖的對偶圖平面圖的對偶圖定義定義17.7 設設g是某平面圖的某個平面嵌入，構造是某平面圖的某個平面嵌入，構造g的對偶圖的對偶圖g*如下：如下：(1) 在在g的面的面ri中放置中放置g*的頂點的頂點v*i. (2) 設設e為為g的任意一條邊的任意一條邊. 若若e在在g的面的面 ri與與 rj 的公共邊界上，做的公共邊界上，做g*的邊的邊e*與與e相相 交，且交，且e*關聯關聯g*的位于的位于ri與與rj中的頂點中的

16、頂點v*i與與v*j，即，即 e*=(v*i,v*j)， e*不與其它任何邊相交不與其它任何邊相交. 若若e為為g中的橋且在面中的橋且在面ri的邊界上，則的邊界上，則e*是以是以ri中中g*的頂的頂 點點v*i為端點的環(huán)，即為端點的環(huán)，即e*=(v*i,v*i). 18下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖. 實例實例19g 的對偶圖的對偶圖g*有以下性質：有以下性質：(1) g*是平面圖，而且是平面嵌入是平面圖，而且是平面嵌入.(2) g*是連通圖是連通圖(3) 若邊若邊e為為g中的環(huán)，則中的環(huán)，則g*與與e對應的邊對應的邊e*為橋，

17、若為橋，若e為橋，為橋，則則g*中與中與e對應的邊對應的邊e*為環(huán)為環(huán).(4) 在多數情況下，在多數情況下，g*為多重圖（含平行邊的圖）為多重圖（含平行邊的圖）.(5) 同構的平面圖（平面嵌入）的對偶圖不一定是同構的同構的平面圖（平面嵌入）的對偶圖不一定是同構的. 如上面的例子如上面的例子. 對偶圖的性質對偶圖的性質20平面圖與對偶圖的平面圖與對偶圖的階數、邊數與面數之間的關系階數、邊數與面數之間的關系定理定理17.17 設設g*是連通平面圖是連通平面圖g的對偶圖，的對偶圖，n*, m*, r*和和n, m, r分別為分別為g*和和g的頂點數、邊數和面數，則的頂點數、邊數和面數，則(1) n*

18、= r(2) m*=m(3) r*=n(4) 設設g*的頂點的頂點v*i位于位于g的面的面ri中，則中，則dg*(v*i)=deg(ri)證明線索證明線索(1)、(2)平凡平凡.(3) 應用歐拉公式應用歐拉公式.(4) 的證明中注意，橋只能在某個面的邊界中，非橋邊在兩的證明中注意，橋只能在某個面的邊界中，非橋邊在兩個面的邊界上個面的邊界上. 21平面圖與對偶圖的平面圖與對偶圖的階數、邊數與面數之間的關系階數、邊數與面數之間的關系定理定理17.18 設設g*是具有是具有k（k 2）個連通分支的平面圖）個連通分支的平面圖g的對的對偶圖，則偶圖，則(1) n*= r(2) m*=m(3) r*=n

19、k+1(4) 設設g*的頂點的頂點v*i位于位于g的面的面ri中，則中，則dg*(v*i)=deg(ri)其中其中n*, m*, r*, n, m, r同定理同定理17.17. 證明證明(3) 時應同時應用歐拉公式及歐拉公式的推廣時應同時應用歐拉公式及歐拉公式的推廣. 22自對偶圖自對偶圖定義定義17.8 設設g*是平面圖是平面圖g的對偶圖，若的對偶圖，若g* g，則稱，則稱g為為自自對偶圖對偶圖. 輪圖輪圖定義如下：定義如下：在在n 1（n 4）邊形）邊形cn 1內放置內放置1個頂點，使這個頂點與個頂點，使這個頂點與cn 1上的所有的頂點均相鄰上的所有的頂點均相鄰. 所得所得n 階簡單圖稱為

20、階簡單圖稱為n階輪圖階輪圖. n為奇為奇數的輪圖稱為數的輪圖稱為奇階輪圖奇階輪圖，n為偶數的輪圖稱為為偶數的輪圖稱為偶階輪圖偶階輪圖，常，常將將 n 階輪圖記為階輪圖記為wn. 輪圖都是自對偶圖輪圖都是自對偶圖. 圖中給出了圖中給出了w6和和w7. 請畫出它們的對偶圖，請畫出它們的對偶圖，從而說明它們都是自對偶圖從而說明它們都是自對偶圖. 23第十七章第十七章 習題課習題課主要內容主要內容l 平面圖的基本概念平面圖的基本概念l 歐拉公式歐拉公式l 平面圖的判斷平面圖的判斷l(xiāng) 平面圖的對偶圖平面圖的對偶圖基本要求基本要求l 深刻理解本部分的基本概念：平面圖、平面嵌入、面、深刻理解本部分的基本概念

21、：平面圖、平面嵌入、面、次數、極大平面圖、極小非平面圖、對偶圖次數、極大平面圖、極小非平面圖、對偶圖l 牢記極大平面圖的主要性質和判別方法牢記極大平面圖的主要性質和判別方法l 熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式熟記歐拉公式及推廣形式，并能用歐拉公式及推廣形式證明有關定理與命題證明有關定理與命題l 會用庫拉圖斯基定理證明某些圖不是平面圖會用庫拉圖斯基定理證明某些圖不是平面圖 l 記住平面圖與它的對偶圖階數、邊數、面數之間的關系記住平面圖與它的對偶圖階數、邊數、面數之間的關系24練習練習1解解 設設g的階數、邊數、面數分別為的階數、邊數、面數分別為n, m, r. (1) 否則，由歐

22、拉公式得否則，由歐拉公式得 2m 5r = 5 (2+m n) 由于由于 (g) 3及握手定理又有及握手定理又有 2m 3n 由由與與得得 m 30 又有又有 r=2+m n 12 由由及及又可得又可得 m30 ,是矛盾的是矛盾的. (2) 正十二面體是一個反例正十二面體是一個反例 1. 設設g是連通的簡單的平面圖，面數是連通的簡單的平面圖，面數r12， (g) 3. (1) 證明證明g中存在次數中存在次數 4的面的面(2) 舉例說明當舉例說明當r=12時，時，(1) 中結論不真中結論不真.252. 設設g是階數是階數n 11的無向平面圖，證明的無向平面圖，證明g和和 不可能全是不可能全是平面圖平面圖. g證證 只需證明只需證明g和和 中至少有一個是非平面圖中至少有一個是非平面圖. 采用反證法采用反證法. 否則否則 與與g 都是平面圖，下面來推出矛盾都是平面圖，下面來推出矛盾.g與與 的邊數的邊數m, m 應滿足應滿足 ( kn的邊數的邊數) 由鴿巢原理知由鴿巢原理知m或或m ，不妨設，不妨設