《離散數(shù)學(xué)圖論》(1)ppt課件

1、第十七章第十七章 平面圖平面圖v本章的主要內(nèi)容本章的主要內(nèi)容v平面圖的根本概念平面圖的根本概念v歐拉公式歐拉公式v平面圖的判別平面圖的判別v平面圖的對偶圖平面圖的對偶圖在圖中，在圖中，(2)是是(1) 的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入.17.1 17.1 平面圖的根本概念平面圖的根本概念定義定義:1. G是可平面圖或平面圖是可平面圖或平面圖將將G除頂點外無邊相交地畫在平除頂點外無邊相交地畫在平面上。面上。2. 平面嵌入平面嵌入畫出的無邊相交的平面圖。畫出的無邊相交的平面圖。3. 非平面圖非平面圖無平面嵌入的無向圖。無平面嵌入的無向圖。 (1) (2) (3) (4)

2、幾點闡明及一些簡單結(jié)論幾點闡明及一些簡單結(jié)論v 普通所談平面圖不一定是指平面嵌入，上圖中普通所談平面圖不一定是指平面嵌入，上圖中4個圖都個圖都是平面圖，但討論某些性質(zhì)時，一定是指平面嵌入是平面圖，但討論某些性質(zhì)時，一定是指平面嵌入. v 結(jié)論：結(jié)論： v (1) K5, K3,3都不是平面圖待證都不是平面圖待證v (2) 設(shè)設(shè)GG，假設(shè)，假設(shè)G為平面圖，那么為平面圖，那么G也是平面圖也是平面圖定理定理17.1v (3) 設(shè)設(shè)GG，假設(shè)，假設(shè)G為非平面圖，那么為非平面圖，那么G也是非平也是非平面圖定理面圖定理17.2，由此可知，由此可知，Kn(n6)，K3,n(n4) 都是非平面圖。都是非平面圖

3、。 v (4) 平行邊與環(huán)不影響平面性平行邊與環(huán)不影響平面性. v1 v5v4 v2 v3 3 51 62 4 a fb ec d平面圖平面圖(平面嵌入平面嵌入)的面與次數(shù)的面與次數(shù)定義：定義： 1. G的面的面G的平面嵌入的邊將平面化分成的假設(shè)干區(qū)域的平面嵌入的邊將平面化分成的假設(shè)干區(qū)域2. 無限面或外部面無限面或外部面可用可用R0表示表示面積無限的面面積無限的面3. 有限面或內(nèi)部面可用有限面或內(nèi)部面可用R1, R2, , Rk等表示等表示面積面積 有限的面有限的面 4. 面面 Ri 的邊境的邊境包圍包圍Ri的回路組的回路組5. 面面 Ri 的次數(shù)的次數(shù)Ri邊境的長度，用邊境的長度，用deg

4、(Ri)表示表示 A DFB Cr1r2r3r0 r1 : 邊境邊境: ABCDFDA deg(r1)=6r2 : 邊境邊境: ABCA deg(r2)=3r3 : 邊境邊境: ACDA deg(r3)=3r0 : 邊境邊境: ADA deg(r0)=2定理定理17.4 平面圖各面次數(shù)之和等于邊數(shù)的兩倍。平面圖各面次數(shù)之和等于邊數(shù)的兩倍。 幾點闡明幾點闡明v 假設(shè)平面圖假設(shè)平面圖G有有k個面，可籠統(tǒng)地用個面，可籠統(tǒng)地用R1, R2, , Rk表示，表示，不需求指出外部面不需求指出外部面.v 定義中回路組是指：邊境能夠是初級回路定義中回路組是指：邊境能夠是初級回路(圈圈)，能夠是簡，能夠是簡單回

5、路，也能夠是復(fù)雜回路。特別地，還能夠是非連通的單回路，也能夠是復(fù)雜回路。特別地，還能夠是非連通的回路之并回路之并. 平面圖有平面圖有4個面，個面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 請寫各面的邊境。請寫各面的邊境。 極大平面圖極大平面圖定義：假設(shè)在簡單平面圖定義：假設(shè)在簡單平面圖G中的恣意兩個不相鄰的頂點之間中的恣意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖，那么稱加一條新邊所得圖為非平面圖，那么稱G為極大平面圖為極大平面圖.留意：假設(shè)簡單平面圖留意：假設(shè)簡單平面圖G中已無不相鄰頂點，中已無不相鄰頂點，G顯然是極大顯然是極大平平面圖，如面

6、圖，如K1(平凡圖平凡圖), K2, K3, K4都是極大平面圖。都是極大平面圖。v極大平面圖的主要性質(zhì)極大平面圖的主要性質(zhì)v定理定理17.5 極大平面圖是連通的。極大平面圖是連通的。v證明思緒：否那么，加新邊不破壞平面性證明思緒：否那么，加新邊不破壞平面性定理定理17.6 nn3階極大平面圖中不能夠有割點和橋。階極大平面圖中不能夠有割點和橋。 證明思緒：由定理證明思緒：由定理17.5及及n3可知，可知，G中假設(shè)有橋，那么中假設(shè)有橋，那么一定有割點，因此只需證無割點即可一定有割點，因此只需證無割點即可. 方法還是反證法。方法還是反證法。證明：證明：(1) 由于由于n 3, 又又G必為簡單必為簡

7、單平面圖可知，平面圖可知，G每個面的每個面的次數(shù)均次數(shù)均 3.(2) 由于由于G為平面圖，又為極為平面圖，又為極大平面圖大平面圖. 可證可證G不能夠不能夠存在次數(shù)存在次數(shù)3的面的面. 就給出的圖討論即可就給出的圖討論即可. 極大平面圖的性質(zhì)極大平面圖的性質(zhì)定理定理17.7 設(shè)設(shè)G為為nn3階極大平面圖，那么階極大平面圖，那么G的每個面的的每個面的次數(shù)均為次數(shù)均為3。 定理定理17.7中的條件也是極大平面圖的充分條件。中的條件也是極大平面圖的充分條件。 定理定理17.7 設(shè)設(shè)G為為n (n3) 階平面圖，且每個面的次數(shù)均為階平面圖，且每個面的次數(shù)均為3，那么，那么G為極大平面圖為極大平面圖.定理

8、的運用定理的運用上圖中，只需上圖中，只需(3)為極大平面圖為極大平面圖 (1) (2) (3) 極小非平面圖極小非平面圖定義：假設(shè)在非平面圖定義：假設(shè)在非平面圖G中恣意刪除一條邊，所得圖中恣意刪除一條邊，所得圖G為平為平面圖，那么稱面圖，那么稱G為極小非平面圖為極小非平面圖.由定義不難看出：由定義不難看出：(1) K5, K3,3都是極小非平面圖都是極小非平面圖(2) 極小非平面圖必為簡單圖極小非平面圖必為簡單圖圖中所示各圖都是極小非平面圖圖中所示各圖都是極小非平面圖. .定理定理17.9 歐拉公式的推行設(shè)歐拉公式的推行設(shè)G是具有是具有kk 2個連通個連通分支的平面圖，那么分支的平面圖，那么n

9、 m+r=k+1證明中對各連通分支用歐拉公式，并留意證明中對各連通分支用歐拉公式，并留意即可即可. kiikrr1)1(17.2 17.2 歐拉公式歐拉公式定理定理17.8 設(shè)設(shè)G為為n階階m條邊條邊r個面的連通平面圖，那么個面的連通平面圖，那么nm+r=2此公式稱為歐拉公式此公式稱為歐拉公式證證 對邊數(shù)對邊數(shù)m做歸納法做歸納法m=0，G為平凡圖，結(jié)論為真為平凡圖，結(jié)論為真.設(shè)設(shè)m=kk1結(jié)論為真，結(jié)論為真，m=k+1時分情況討論時分情況討論.(1) G中無圈，那么中無圈，那么G為樹，刪除一片樹葉，用歸納假設(shè)為樹，刪除一片樹葉，用歸納假設(shè).(2) 否那么，在某一個圈上刪除一條邊，進展討論否那么

10、，在某一個圈上刪除一條邊，進展討論.)2(2 nllm)2()deg(21nmlrlRmrii )2(2 nllm)1(2 knllm解得解得 也可得：也可得： 定理定理17.11 在具有在具有kk2個連通分支的平面圖中，個連通分支的平面圖中，與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理定理定理17.10 設(shè)設(shè)G為連通的平面圖，且為連通的平面圖，且deg(Ri)l, l3，那么，那么 證明：由定理證明：由定理17.4及歐拉公式得及歐拉公式得推論推論 K5, K3,3不是平面圖不是平面圖.63 nm定理定理17.12 設(shè)設(shè)G為為nn3階階m條邊的簡單平面圖，那么條邊的簡單平面圖，那么m3n6. 證明

11、：設(shè)證明：設(shè)G有有kk1個連通分支，假設(shè)個連通分支，假設(shè)G為樹或森林，當為樹或森林，當n3時，時，m3n6為真為真. 否那么否那么G中含圈，每個面至少由中含圈，每個面至少由ll3條邊圍成，又條邊圍成，又2212 lll定理定理17.13 設(shè)設(shè)G為為nn 3階階m條邊的極大平面圖，那么條邊的極大平面圖，那么m=3n 6.證明：由定理證明：由定理17.4, 歐拉公式及定理歐拉公式及定理17.7所證。所證。 定理定理17.14 設(shè)設(shè)G 為簡單平面圖，那么為簡單平面圖，那么 (G) 5. 證明：證明： 階數(shù)階數(shù) n 6，結(jié)論為真。，結(jié)論為真。 當當n 7 時，用反證法。否那么時，用反證法。否那么會推出

12、會推出2m 6n m 3n，這與定理，這與定理17.12矛盾矛盾. 與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理在在l=3到達最大值，由定理到達最大值，由定理17.11可知可知m3n6.17.3 17.3 平面圖的判別平面圖的判別1. 插入插入2度頂點和消去度頂點和消去2度頂點度頂點定義：定義：(1) 消去消去2度頂點度頂點v，見以下圖中，由，見以下圖中，由(1) 到到(2) (2) 插入插入2度頂點度頂點v，見以下圖中，從，見以下圖中，從(2) 到到(1) . (1) (2) 2. 圖之間的同胚圖之間的同胚定義：假設(shè)定義：假設(shè)G1G2，或經(jīng)過反復(fù)插入或消去，或經(jīng)過反復(fù)插入或消去2度頂點后度頂點后

13、所得所得G1G2，那么稱，那么稱G1與與G2同胚同胚. 圖的同胚圖的同胚定理定理17.15 (Kuratowski定理定理) G是平面圖是平面圖 G中不含與中不含與K5或或K3,3同胚的子圖。同胚的子圖。(1) (2) 子圖子圖 (1) (2) 平面圖斷定定理平面圖斷定定理判別下面彼得森判別下面彼得森(Peterser)圖圖: v1v6v2v5v8v9v3v4v7v10v1v6v2v5v8v9v3v4v7v10v1v8v9v2v6v5v10v4v3v717.4 17.4 平面圖的對偶圖平面圖的對偶圖定義：設(shè)定義：設(shè)G是某平面圖的某個平面嵌入，構(gòu)造是某平面圖的某個平面嵌入，構(gòu)造G的對偶圖的對偶圖

14、G*如下：如下：(1) 在在G的面的面Ri中放置中放置G*的頂點的頂點v*i. (2) 設(shè)設(shè)e為為G的恣意一條邊的恣意一條邊. 假設(shè)假設(shè)e在在G的面的面 Ri與與 Rj 的公共邊境上，做的公共邊境上，做G*的邊的邊e*與與e相相 交，且交，且e*關(guān)聯(lián)關(guān)聯(lián)G*的位于的位于Ri與與Rj中的頂點中的頂點v*i與與v*j，即，即 e*=(v*i,v*j)， e*不與其它任何邊相交不與其它任何邊相交. 假設(shè)假設(shè)e為為G中的橋且在面中的橋且在面Ri的邊境上，那么的邊境上，那么e*是以是以Ri中中G*的頂?shù)捻?點點v*i為端點的環(huán)，即為端點的環(huán)，即e*=(v*i,v*i). 下面兩圖中，實線邊圖為平面圖，虛

15、線邊圖為其對偶圖下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖. . 實例實例v G 的對偶圖的對偶圖G*有以下性質(zhì)：有以下性質(zhì)：v (1) G*是平面圖，而且是平面嵌入。是平面圖，而且是平面嵌入。v (2) G*是連通圖是連通圖v (3) 假設(shè)邊假設(shè)邊e為為G中的環(huán)，那么中的環(huán)，那么G*與與e對應(yīng)的邊對應(yīng)的邊e*為橋，假設(shè)為橋，假設(shè)e為橋，那么為橋，那么G*中與中與e對應(yīng)的邊對應(yīng)的邊e*為環(huán)。為環(huán)。v (4) 在多數(shù)情況下，在多數(shù)情況下，G*為多重圖含平行邊的圖。為多重圖含平行邊的圖。v (5) 同構(gòu)的平面圖平面嵌入的對偶圖不一定是同構(gòu)的。同構(gòu)的平面圖平面嵌入的對偶圖不一定是同構(gòu)的。v 如

16、上面的例子。如上面的例子。 對偶圖的性質(zhì)對偶圖的性質(zhì)平面圖與對偶圖之間的關(guān)系平面圖與對偶圖之間的關(guān)系定理定理17.17 設(shè)設(shè)G*是連通平面圖是連通平面圖G的對偶圖，的對偶圖，n*, m*, r*和和n, m, r分別為分別為G*和和G的頂點數(shù)、邊數(shù)和面數(shù)，那么的頂點數(shù)、邊數(shù)和面數(shù)，那么(1) n*= r(2) m*=m(3) r*=n(4) 設(shè)設(shè)G*的頂點的頂點v*i位于位于G的面的面Ri中，那么中，那么d(v*i)=deg(Ri)證明：證明：(1)、(2)平凡平凡(3) 運用歐拉公式運用歐拉公式(4) 的證明中留意，橋只能在某個面的邊境中，非橋邊在兩的證明中留意，橋只能在某個面的邊境中，非橋

17、邊在兩個面的邊境上。個面的邊境上。 平面圖與對偶圖的關(guān)系平面圖與對偶圖的關(guān)系定理定理17.18 設(shè)設(shè)G*是具有是具有kk2個連通分支的平面圖個連通分支的平面圖G的的對對偶圖，那么偶圖，那么(1) n*= r(2) m*=m(3) r*=nk+1(4) 設(shè)設(shè)G*的頂點的頂點v*i位于位于G的面的面Ri中，那么中，那么d(v*i)=deg(Ri)其中其中n*, m*, r*, n, m, r同定理同定理17.17. 證明證明(3) 時應(yīng)同時運用歐拉公式及歐拉公式的推行。時應(yīng)同時運用歐拉公式及歐拉公式的推行。 自對偶圖自對偶圖定義：設(shè)定義：設(shè)G*是平面圖是平面圖G的對偶圖，假設(shè)的對偶圖，假設(shè)G*G，

18、那么稱，那么稱G為為自自對偶圖對偶圖. 概念：概念： n階輪圖階輪圖 Wn 、奇階輪圖、偶階輪圖、奇階輪圖、偶階輪圖輪圖都是自對偶圖。輪圖都是自對偶圖。畫出畫出W6和和W7的對偶圖，并闡明它們都是自對偶圖。的對偶圖，并闡明它們都是自對偶圖。 第十七章第十七章 小結(jié)小結(jié)v 主要內(nèi)容主要內(nèi)容v 平面圖的根本概念平面圖的根本概念v 歐拉公式歐拉公式v 平面圖的判別平面圖的判別v 平面圖的對偶圖平面圖的對偶圖v 根本要求根本要求v 了解根本概念：平面圖、平面嵌入、面、次數(shù)、極大平面了解根本概念：平面圖、平面嵌入、面、次數(shù)、極大平面圖、極小非平面圖、對偶圖圖、極小非平面圖、對偶圖v 牢記極大平面圖的主要

19、性質(zhì)和判別方法牢記極大平面圖的主要性質(zhì)和判別方法v 熟記歐拉公式及推行，并能用歐拉公式及推行方式證明有熟記歐拉公式及推行，并能用歐拉公式及推行方式證明有關(guān)定理與命題關(guān)定理與命題v 會用庫拉圖斯基定理證明某些圖不是平面圖會用庫拉圖斯基定理證明某些圖不是平面圖 v 記住平面圖與它的對偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系記住平面圖與它的對偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系練習(xí)練習(xí)1 1解解 設(shè)設(shè)G的階數(shù)、邊數(shù)、面數(shù)分別為的階數(shù)、邊數(shù)、面數(shù)分別為n, m, r. (1) 否那么，由歐拉公式得否那么，由歐拉公式得 2m 5r = 5 (2+mn) 由于由于(G)3及握手定理又有及握手定理又有 2m 3n 由與得由

20、與得 m30 又有又有 r=2+mn 12 由及又可得由及又可得 m30 ,是矛盾的是矛盾的. (2) 正十二面體是一個反例正十二面體是一個反例 1. 設(shè)設(shè)G是連通的簡單的平面圖，面數(shù)是連通的簡單的平面圖，面數(shù)r12，(G)3. (1) 證明證明G中存在次數(shù)中存在次數(shù)4的面的面 (2) 舉例闡明當舉例闡明當r=12時，時，(1) 中結(jié)論不真中結(jié)論不真.2. 設(shè)設(shè)G是階數(shù)是階數(shù)n11的無向平面圖，證明的無向平面圖，證明G和和 不能夠全不能夠全是平面圖是平面圖. G證證 只需證明只需證明G和和 中至少有一個是非平面圖中至少有一個是非平面圖. 采用反證法采用反證法. 否那么否那么 與與G 都是平面圖，下面來推出矛盾都是平面圖，下面來推出矛盾.G與與 的邊數(shù)的邊數(shù)m, m應(yīng)滿足應(yīng)滿足 ( Kn