離散數(shù)學(xué)平面圖

1、第17章 平面圖離離 散散 數(shù)數(shù) 學(xué)學(xué)中國地質(zhì)大學(xué)本科生課程中國地質(zhì)大學(xué)本科生課程本章說明本章說明q本章的主要內(nèi)容本章的主要內(nèi)容平面圖的基本概念平面圖的基本概念歐拉公式歐拉公式平面圖的判斷平面圖的判斷平面圖的對(duì)偶圖平面圖的對(duì)偶圖本章所涉及到的圖均指無向圖。本章所涉及到的圖均指無向圖。q 17.1 17.1 平面圖的基本概念平面圖的基本概念q 17.2 17.2 歐拉公式歐拉公式q 17.3 17.3 平面圖的判斷平面圖的判斷q 17.4 17.4 平面圖的對(duì)偶圖平面圖的對(duì)偶圖q 本章小結(jié)本章小結(jié)q 習(xí)習(xí) 題題q 作作 業(yè)業(yè)17.1 平面圖的基本概念平面圖的基本概念一、關(guān)于平面圖的一些基本概念一

2、、關(guān)于平面圖的一些基本概念1、 平面圖的定義平面圖的定義定義定義17.117.1 q G可嵌入曲面可嵌入曲面S如果圖如果圖G能以這樣的方式畫在曲面能以這樣的方式畫在曲面S上，上，即除頂點(diǎn)處外無邊相交。即除頂點(diǎn)處外無邊相交。 q G是可平面圖或平面圖是可平面圖或平面圖若若G可嵌入平面可嵌入平面。q G的平面嵌入的平面嵌入畫出的無邊相交的平面圖。畫出的無邊相交的平面圖。q 非平面圖非平面圖無平面嵌入的圖。無平面嵌入的圖。（2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。2、 幾點(diǎn)說明及一些簡單結(jié)論幾點(diǎn)說明及一些簡單結(jié)論q 一般所談平面圖不一定是指平面嵌入，

3、但討論某些性質(zhì)時(shí)，一般所談平面圖不一定是指平面嵌入，但討論某些性質(zhì)時(shí)，一定是指平面嵌入。一定是指平面嵌入。q K5和和K3,3都不是平面圖。都不是平面圖。q 定理定理17.117.1 設(shè)設(shè)GG，若若G為平面圖，則為平面圖，則G 也是平面圖。也是平面圖。q 設(shè)設(shè)GG，若若G 為非平面圖，則為非平面圖，則G也是非平面圖。也是非平面圖。q 由定理可知，由定理可知， Kn(n 5)和和K3,n(n 3)都是非平面圖。都是非平面圖。q 定理定理17.17.2 2 若若G為平面圖，則在為平面圖，則在G中加平行邊或環(huán)所得圖還是中加平行邊或環(huán)所得圖還是平面圖。平面圖。即平行邊和環(huán)不影響圖的平面性。即平行邊和環(huán)

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

5、i)。2、幾點(diǎn)說明、幾點(diǎn)說明q 若平面圖若平面圖G有有k個(gè)面，可籠統(tǒng)地用個(gè)面，可籠統(tǒng)地用R1, R2, , Rk表示，不需表示，不需要指出外部面。要指出外部面。q 回路組是指：邊界可能是初級(jí)回路（圈），可能是簡單回回路組是指：邊界可能是初級(jí)回路（圈），可能是簡單回路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路路，也可能是復(fù)雜回路。特別地，還可能是非連通的回路之并。之并。平面圖有平面圖有4個(gè)面，個(gè)面，deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8。 R1R2R3R0定理定理17.17.3 3 平面圖平面圖G中所有面的次數(shù)之和等于邊數(shù)中所有面的次數(shù)之和等于

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

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

8、) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖為極大平面圖當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為的每個(gè)面的次數(shù)均為3。q本節(jié)只證明必要性，即本節(jié)只證明必要性，即設(shè)設(shè)G為為n(n 3) )階簡單連通的平面圖，階簡單連通的平面圖，G為極大平面圖，則為極大平面圖，則G的每個(gè)面的次數(shù)均為的每個(gè)面的次數(shù)均為3。q由于由于n 3, 又又G必為簡單平面圖，可知，必為簡單平面圖，可知，G每個(gè)面的次數(shù)均每個(gè)面的次數(shù)均 3。q因?yàn)橐驗(yàn)镚為平面圖，又為極大平面圖?？勺C為平面圖，又為極大平面圖。可證G不可能存在次數(shù)不可能存在次數(shù)3的面。的面。證證明明思思路路假設(shè)存在面假設(shè)存在面Ri的次數(shù)的次數(shù)deg(Ri

9、)=s4，如圖所示。如圖所示。在在G中，若中，若v1與與v3不相鄰，在不相鄰，在Ri內(nèi)加邊內(nèi)加邊(v1,v3)不破壞平面性，這不破壞平面性，這與與G是極大平面圖矛盾，因而是極大平面圖矛盾，因而v1與與v3必相鄰，由于必相鄰，由于Ri的存在，的存在，邊邊(v1,v3)必在必在Ri外。外。 類似地，類似地，v2與與v4也必相鄰，且邊也必相鄰，且邊(v2,v4)也必在也必在Ri外部，于是必外部，于是必產(chǎn)生產(chǎn)生(v1,v3)與與(v2,v4)相交于相交于Ri的外部，這又矛盾于的外部，這又矛盾于G是平面圖，是平面圖，所以必有所以必有s3，即即G中不存在次數(shù)大于或等于中不存在次數(shù)大于或等于4的面，所以的面

10、，所以G的的每個(gè)面為每個(gè)面為3條邊所圍，也就是各面次數(shù)均為條邊所圍，也就是各面次數(shù)均為3。sS-1 只有右邊的圖為極大平面圖。只有右邊的圖為極大平面圖。 因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為3。 四、極小非平面圖四、極小非平面圖定義定義17.417.4 若在非平面圖若在非平面圖G中任意刪除一條邊，所得圖中任意刪除一條邊，所得圖G為平面為平面圖，則稱圖，則稱G為極小非平面圖。為極小非平面圖。由定義不難看出：由定義不難看出：q K5, K3,3都是極小非平面圖。都是極小非平面圖。q 極小非平面圖必為簡單圖。極小非平面圖必為簡單圖。例如：例如：以下各圖均為極小非平面圖。以下各圖均

11、為極小非平面圖。小節(jié)結(jié)束小節(jié)結(jié)束17.2 17.2 歐拉公式歐拉公式 一、歐拉公式相關(guān)定理一、歐拉公式相關(guān)定理1、 歐拉公式歐拉公式定理定理17.17.6 6 對(duì)于任意的連通的平面圖對(duì)于任意的連通的平面圖G，有有n-m+r=2其中，其中，n、m、r分別為分別為G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。 證明證明對(duì)邊數(shù)對(duì)邊數(shù)m作歸納法。作歸納法。 (1) m0時(shí)，由于時(shí)，由于G為連通圖，所以為連通圖，所以G只能是由一個(gè)孤立頂只能是由一個(gè)孤立頂點(diǎn)組成的平凡圖，即點(diǎn)組成的平凡圖，即n=1，m=0，r=1，結(jié)論顯然成立。結(jié)論顯然成立。(2) m1時(shí)，由于時(shí)，由于G為連通圖，所以為連通圖，所以n=2

12、，m=1，r=1，結(jié)論結(jié)論顯然成立。顯然成立。 (3)設(shè)設(shè)mk(k1)時(shí)成立，當(dāng)時(shí)成立，當(dāng)mk+1時(shí)，對(duì)時(shí)，對(duì)G進(jìn)行如下討論。進(jìn)行如下討論。q 若若G是樹，則是樹，則G是非平凡的，因而是非平凡的，因而G中至少有兩片樹葉。中至少有兩片樹葉。 設(shè)設(shè)v為樹葉，令為樹葉，令G=G-v，則則G仍然是連通圖，且仍然是連通圖，且G的邊數(shù)的邊數(shù)m=m-1=k，n=n-1，r=r。 由假設(shè)可知由假設(shè)可知 n-m+r=2，式中式中n，m，r分別為分別為G的頂點(diǎn)數(shù)，的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。邊數(shù)和面數(shù)。 于是于是n-m+r=(n+1)-(m+1)+r=n-m+r=2q 若若G不是樹，則不是樹，則G中含圈。中含圈。 設(shè)邊

13、設(shè)邊e在在G中某個(gè)圈上，令中某個(gè)圈上，令G=G-e，則則G仍連通且仍連通且m=m-1=k， n=n，r=r-1。 由假設(shè)有由假設(shè)有 n-m+r=2。 于是于是 n-m+r=n-(m+1)-(r+1)=n-m+r=2 定理定理17.17.7 7 對(duì)于具有對(duì)于具有k(k2)個(gè)連通分支的平面圖個(gè)連通分支的平面圖G，有有 n-m+r = k+1其中其中n，m，r分別為分別為G的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。的頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。 證明證明 設(shè)設(shè)G的連通分支分別為的連通分支分別為G1、G2、Gk，并設(shè)并設(shè)Gi的頂點(diǎn)數(shù)、邊的頂點(diǎn)數(shù)、邊數(shù)、面數(shù)分別為數(shù)、面數(shù)分別為ni、mi、ri、i=1，2，k。 由歐拉公式可知由歐

14、拉公式可知: ni-mi+ri = 2，i=1，2，k (17.1)易知，易知，11kkiiiimmnn，由于每個(gè)由于每個(gè)Gi 有一個(gè)外部面，而有一個(gè)外部面，而G只有一個(gè)外部面，所以只有一個(gè)外部面，所以G的面數(shù)的面數(shù)11kiirrk于是，于是，對(duì)對(duì)(17.1)的兩邊同時(shí)求和得的兩邊同時(shí)求和得 11112()1kkkkiiiiiiiiiiknmrnmrnmrk 經(jīng)整理得經(jīng)整理得 n-m+r = k+1。2、 與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理定理定理17.17.8 8 設(shè)設(shè)G為連通的平面圖，且每個(gè)面的次數(shù)至少為為連通的平面圖，且每個(gè)面的次數(shù)至少為l(l3)，則則 G的邊數(shù)與頂點(diǎn)數(shù)有如下關(guān)系

15、：的邊數(shù)與頂點(diǎn)數(shù)有如下關(guān)系：由定理由定理17.3（面的次數(shù)之和等于邊數(shù)的（面的次數(shù)之和等于邊數(shù)的2倍）及歐拉公式得倍）及歐拉公式得(2)2lmnl證明證明12deg()(2)riimRl rlmn 解得解得 (2)2lmnl推論推論 K5, K3,3不是平面圖。不是平面圖。證明證明q若若K5是平面圖，由于是平面圖，由于K5中無環(huán)和平行邊，所以每個(gè)面的次數(shù)中無環(huán)和平行邊，所以每個(gè)面的次數(shù)均大于或等于均大于或等于l3，由由定理定理17.8可知邊數(shù)可知邊數(shù)10應(yīng)滿足應(yīng)滿足 10(3/(3-2)(5-2) = 9 這是個(gè)矛盾，所以這是個(gè)矛盾，所以K5不是平面圖。不是平面圖。 q若若K3,3是平面圖，由

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

17、或森林，當(dāng)為樹或森林，當(dāng)n 3時(shí)，時(shí)，m=n-k 3n 6為真。為真。q 若若G不是樹也不是森林，則不是樹也不是森林，則G中必含圈，又因?yàn)橹斜睾?，又因?yàn)镚是簡單圖，是簡單圖，所以，每個(gè)面至少由所以，每個(gè)面至少由l（l 3）條邊圍成，又在條邊圍成，又在l=3達(dá)到最大值達(dá)到最大值，由定理，由定理17.9可知可知證明證明2(1)(1)(1)3(2)3622lmnknknnll定理定理17.117.11 1 設(shè)設(shè)G為為n(n 3)階階m條邊的極大平面圖，則條邊的極大平面圖，則m=3n 6。證明證明 由于極大平面圖是連通圖，由歐拉公式得由于極大平面圖是連通圖，由歐拉公式得: r=2+m-n (17.4

18、) 又因?yàn)橛忠驗(yàn)镚是極大平面圖，由定理是極大平面圖，由定理17.7的必要性可知，的必要性可知，G的每個(gè)的每個(gè)面的次數(shù)均為面的次數(shù)均為3，所以：，所以： 將將(17.4)代入代入(17.5)，整理后得，整理后得 m = 3n-6。12deg()3(17.5)riimRr二、一個(gè)意義重大的定理二、一個(gè)意義重大的定理 定理定理17.117.12 2 設(shè)設(shè)G為簡單平面圖，則為簡單平面圖，則G的最小度的最小度 (G) 5。q 若階數(shù)若階數(shù) n 6，結(jié)論顯然成立。結(jié)論顯然成立。q 若階數(shù)若階數(shù)n 7時(shí)，用反證法。時(shí)，用反證法。 假設(shè)假設(shè) (G) 6，由握手定理可知：由握手定理可知：證明證明12( )6ni

19、imd vn因而因而m 3n，這與定理這與定理17.10矛盾。矛盾。所以，假設(shè)不成立，即所以，假設(shè)不成立，即G的最小度的最小度 (G) 5。q本定理在圖著色理論中占重要地位。本定理在圖著色理論中占重要地位。說說明明一、為判斷定理做準(zhǔn)備一、為判斷定理做準(zhǔn)備1、 插入插入2度頂點(diǎn)和消去度頂點(diǎn)和消去2度頂點(diǎn)度頂點(diǎn)定義定義17.517.5 q 設(shè)設(shè)e=(u,v)為圖為圖G的一條邊，在的一條邊，在G中刪除中刪除e，增加新的頂點(diǎn)增加新的頂點(diǎn)w，使使u、v均與均與w相鄰，稱為在相鄰，稱為在G中中插入插入2度頂點(diǎn)度頂點(diǎn)w。q 設(shè)設(shè)w為為G中一個(gè)中一個(gè)2度頂點(diǎn)，度頂點(diǎn)，w與與u、v相鄰，刪除相鄰，刪除w，增加新

20、邊增加新邊(u,v)，稱為在稱為在G中中消去消去2度頂點(diǎn)度頂點(diǎn)w。17.3 17.3 平面圖的判斷平面圖的判斷2、圖之間的同胚、圖之間的同胚若兩個(gè)圖若兩個(gè)圖G1與與G2同構(gòu)，或通過反復(fù)插入或消去同構(gòu)，或通過反復(fù)插入或消去2度頂點(diǎn)后度頂點(diǎn)后是同構(gòu)的，則稱是同構(gòu)的，則稱G1與與G2是是同胚同胚的。的。上面兩個(gè)圖分別與上面兩個(gè)圖分別與K3,3, K5同胚同胚 。二、兩個(gè)判斷定理二、兩個(gè)判斷定理 定理定理17.117.13 3(庫拉圖斯基定理庫拉圖斯基定理1) 圖圖G是平面圖當(dāng)且僅當(dāng)是平面圖當(dāng)且僅當(dāng)G中既不中既不含與含與K5同胚子圖，也不含與同胚子圖，也不含與K3,3同胚子圖。同胚子圖。 定理定理17

21、.117.14 4(庫拉圖斯基定理庫拉圖斯基定理2) 圖圖G是平面圖當(dāng)且僅當(dāng)是平面圖當(dāng)且僅當(dāng)G中既沒中既沒有可以收縮到有可以收縮到K5的子圖，也沒有可以收縮到的子圖，也沒有可以收縮到K3,3的子圖。的子圖。 例例17.117.1 證明彼得松圖不是平面圖。證明彼得松圖不是平面圖。 將彼得松圖頂點(diǎn)標(biāo)順序，見圖將彼得松圖頂點(diǎn)標(biāo)順序，見圖 (1)所示。所示。證證明明還可以這樣證明：還可以這樣證明：用用G表示彼得松圖，令表示彼得松圖，令 G=G-(j,g),(c,d)G如圖如圖 (3)所示，易知它與所示，易知它與K3,3同胚，同胚，在圖中將邊在圖中將邊(a,f), (b,g), (c,h), (d,i)

22、, (e,j)收縮，收縮，所得圖為圖所得圖為圖 (2)所示，它是所示，它是K5，由定理由定理17.16可知，彼得松圖不是平面圖。可知，彼得松圖不是平面圖。由定理由定理17.15可知，可知，G為非平面圖。為非平面圖。例例17.217.2 對(duì)對(duì)K5插入插入2度頂點(diǎn)，或在度頂點(diǎn)，或在K5外放置一個(gè)頂點(diǎn)使其與外放置一個(gè)頂點(diǎn)使其與K5上的若上的若干頂點(diǎn)相鄰，共可產(chǎn)生多少個(gè)干頂點(diǎn)相鄰，共可產(chǎn)生多少個(gè)6階簡單連通非同構(gòu)的非平面圖？階簡單連通非同構(gòu)的非平面圖？ 用插入用插入2度頂點(diǎn)的方法只能產(chǎn)生度頂點(diǎn)的方法只能產(chǎn)生一個(gè)非平面圖，如圖一個(gè)非平面圖，如圖(1)所示。所示。解答解答在在K5外放置一個(gè)頂點(diǎn)，使其與外放

23、置一個(gè)頂點(diǎn)，使其與K5上的上的1個(gè)到個(gè)到5個(gè)頂點(diǎn)相鄰，得個(gè)頂點(diǎn)相鄰，得5個(gè)圖，如圖個(gè)圖，如圖 (2)到到(6)所示。所示。它與它與K5同胚，所以是非平面圖。同胚，所以是非平面圖。它們都含它們都含K5為子圖，由庫拉圖為子圖，由庫拉圖斯基定理可知，它們都是非平斯基定理可知，它們都是非平面圖，并且也滿足其它要求。面圖，并且也滿足其它要求。例例17.317.3 由由K3,3加若干條邊能生成多少個(gè)加若干條邊能生成多少個(gè)6階連通的簡單的非同構(gòu)的非階連通的簡單的非同構(gòu)的非平面圖？平面圖？ 對(duì)對(duì)K3,3加加16條邊所得圖都含條邊所得圖都含K3,3為子圖，由庫拉圖斯基定理可為子圖，由庫拉圖斯基定理可知，它們都是

24、非平面圖。知，它們都是非平面圖。 在加在加2條、加條、加3條、加條、加4條邊時(shí)又各產(chǎn)生兩個(gè)非同構(gòu)的非平面圖，條邊時(shí)又各產(chǎn)生兩個(gè)非同構(gòu)的非平面圖，連同連同K3,3本身共有本身共有10個(gè)滿足要求的非平面圖。其中，綠線邊表示個(gè)滿足要求的非平面圖。其中，綠線邊表示后加的新邊。后加的新邊。 解答解答小節(jié)結(jié)束小節(jié)結(jié)束17.4 17.4 平面圖的對(duì)偶圖平面圖的對(duì)偶圖一、對(duì)偶圖的定義一、對(duì)偶圖的定義定義定義17.17.6 6 設(shè)設(shè)G是某平面圖的某個(gè)平面嵌入，構(gòu)造是某平面圖的某個(gè)平面嵌入，構(gòu)造G的對(duì)偶圖的對(duì)偶圖G*如下：如下：q 在在G的面的面Ri中放置中放置G*的頂點(diǎn)的頂點(diǎn)vi* 。q 設(shè)設(shè)e為為G的任意一條

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

26、是平面嵌入。是平面圖，而且是平面嵌入。q G*是連通圖。是連通圖。q 若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為橋，若為橋，若e為橋，為橋，則則G*中與中與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為環(huán)。為環(huán)。q 在多數(shù)情況下，在多數(shù)情況下，G*為多重圖（含平行邊的圖）。為多重圖（含平行邊的圖）。q 同構(gòu)的平面圖（平面嵌入）的對(duì)偶圖不一定是同構(gòu)的。同構(gòu)的平面圖（平面嵌入）的對(duì)偶圖不一定是同構(gòu)的。二、平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系。二、平面圖與對(duì)偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系。定理定理17.117.15 5 設(shè)設(shè)G*是連通平面圖是連通平面圖G的對(duì)偶圖，的對(duì)偶圖，n*、m*、r

27、*和和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中，則中，則dG*(vi *)=deg(Ri)q (1)、(2)由由G*的構(gòu)造可知是顯然的。的構(gòu)造可知是顯然的。 q (3)由于由于G與與G*都連通，因而滿足歐拉公式都連通，因而滿足歐拉公式: n-m+r = 2 n*-m*+r* = 2 由由(1)、(2)可知，可知， r* = 2+m*-n* = 2+m-r = nq (4)設(shè)設(shè)G的面的面Ri的邊界為的邊界為Ci，設(shè)設(shè)Ci中有中有k1(k10)條橋，條橋，k

28、2個(gè)非橋邊個(gè)非橋邊，于是，于是 Ci的長度為的長度為k2+2k1，即即deg(Ri)k2+2k1，k1條橋?qū)?yīng)條橋?qū)?yīng)vi*處有處有k1個(gè)環(huán)，個(gè)環(huán)，k2條非橋邊對(duì)應(yīng)從條非橋邊對(duì)應(yīng)從vi*處引出處引出k2條邊，條邊，所以所以dG*(vi*)k2+2k1deg(Ri)。證證明明定理定理17.117.16 6 設(shè)設(shè)G*是具有是具有k（k 2）個(gè)連通分支的平面圖個(gè)連通分支的平面圖G的的對(duì)偶圖，對(duì)偶圖， n*, m*, r*, n, m, r分別為分別為G*和和G的頂點(diǎn)數(shù)、邊數(shù)的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，和面數(shù)，（1）n*= r（2）m*=m（3）r*=n k+1（4）設(shè)設(shè)G*的頂點(diǎn)的頂點(diǎn)v*i位于位于G的面的面Ri中，則中，則dG*(v*i)=deg(Ri)三、自對(duì)偶圖三、自對(duì)偶