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

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

2、幾點(diǎn)闡明及一些簡(jiǎn)單結(jié)論幾點(diǎn)闡明及一些簡(jiǎn)單結(jié)論v 普通所談平面圖不一定是指平面嵌入，上圖中普通所談平面圖不一定是指平面嵌入，上圖中4個(gè)圖都個(gè)圖都是平面圖，但討論某些性質(zhì)時(shí)，一定是指平面嵌入是平面圖，但討論某些性質(zhì)時(shí)，一定是指平面嵌入. 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. 無(wú)限面或外部面無(wú)限面或外部面可用可用R0表示表示面積無(wú)限的面面積無(wú)限的面3. 有限面或內(nèi)部面可用有限面或內(nèi)部面可用R1, R2, , Rk等表示等表示面積面積 有限的面有限的面 4. 面面 Ri 的邊境的邊境包圍包圍Ri的回路組的回路組5. 面面 Ri 的次數(shù)的次數(shù)Ri邊境的長(zhǎng)度，用邊境的長(zhǎng)度，用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ù)的兩倍。 幾點(diǎn)闡明幾點(diǎn)闡明v 假設(shè)平面圖假設(shè)平面圖G有有k個(gè)面，可籠統(tǒng)地用個(gè)面，可籠統(tǒng)地用R1, R2, , Rk表示，表示，不需求指出外部面不需求指出外部面.v 定義中回路組是指：邊境能夠是初級(jí)回路定義中回路組是指：邊境能夠是初級(jí)回路(圈圈)，能夠是簡(jiǎn)，能夠是簡(jiǎn)單回

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

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

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

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

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

10、，在某一個(gè)圈上刪除一條邊，進(jìn)展討論.)2(2 nllm)2()deg(21nmlrlRmrii )2(2 nllm)1(2 knllm解得解得 也可得：也可得： 定理定理17.11 在具有在具有kk2個(gè)連通分支的平面圖中，個(gè)連通分支的平面圖中，與歐拉公式有關(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條邊的簡(jiǎn)單平面圖，那么條邊的簡(jiǎn)單平面圖，那么m3n6. 證明

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

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

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

14、G*如下：如下：(1) 在在G的面的面Ri中放置中放置G*的頂點(diǎn)的頂點(diǎn)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中的頂點(diǎn)中的頂點(diǎn)v*i與與v*j，即，即 e*=(v*i,v*j)， e*不與其它任何邊相交不與其它任何邊相交. 假設(shè)假設(shè)e為為G中的橋且在面中的橋且在面Ri的邊境上，那么的邊境上，那么e*是以是以Ri中中G*的頂?shù)捻?點(diǎn)點(diǎn)v*i為端點(diǎn)的環(huán)，即為端點(diǎn)的環(huán)，即e*=(v*i,v*i). 下面兩圖中，實(shí)線邊圖為平面圖，虛

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

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

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

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

19、性質(zhì)和判別方法牢記極大平面圖的主要性質(zhì)和判別方法v 熟記歐拉公式及推行，并能用歐拉公式及推行方式證明有熟記歐拉公式及推行，并能用歐拉公式及推行方式證明有關(guān)定理與命題關(guān)定理與命題v 會(huì)用庫(kù)拉圖斯基定理證明某些圖不是平面圖會(huì)用庫(kù)拉圖斯基定理證明某些圖不是平面圖 v 記住平面圖與它的對(duì)偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系記住平面圖與它的對(duì)偶圖階數(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) 正十二面體是一個(gè)反例正十二面體是一個(gè)反例 1. 設(shè)設(shè)G是連通的簡(jiǎn)單的平面圖，面數(shù)是連通的簡(jiǎn)單的平面圖，面數(shù)r12，(G)3. (1) 證明證明G中存在次數(shù)中存在次數(shù)4的面的面 (2) 舉例闡明當(dāng)舉例闡明當(dāng)r=12時(shí)，時(shí)，(1) 中結(jié)論不真中結(jié)論不真.2. 設(shè)設(shè)G是階數(shù)是階數(shù)n11的無(wú)向平面圖，證明的無(wú)向平面圖，證明G和和 不能夠全不能夠全是平面圖是平面圖. G證證 只需證明只需證明G和和 中至少有一個(gè)是非平面圖中至少有一個(gè)是非平面圖. 采用反證法采用反證法. 否那么否那么 與與G 都是平面圖，下面來(lái)推出矛盾都是平面圖，下面來(lái)推出矛盾.G與與 的邊數(shù)的邊數(shù)m, m應(yīng)滿足應(yīng)滿足 ( Kn