《特殊平面圖與平面圖的對偶》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Email:yc517922@126.com圖論及其應(yīng)用任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院1本次課主要內(nèi)容(一)、一些特殊平面圖(二)、平面圖的對偶圖特殊平面圖與平面圖的對偶圖1、極大平面圖及其性質(zhì)2、極大外平面圖及其性質(zhì)21、極大平面圖及其性質(zhì)(一)、一些特殊平面圖對于一個簡單平面圖來說，在不鄰接頂點對間加邊，當(dāng)邊數(shù)增加到一定數(shù)量時，就會變成非平面圖。這樣，就啟發(fā)我們研究平面圖的極圖問題。定義1設(shè)G是簡單可平面圖，如果G是Ki(1≦i≦4),或者在G的任意非鄰接頂點間添加一條邊后，得到的圖均是非可平面圖

2、，則稱G是極大可平面圖。極大可平面圖的平面嵌入稱為極大平面圖。3注：只有在單圖前提下才能定義極大平面圖。引理設(shè)G是極大平面圖，則G必然連通；若G的階數(shù)大于等于3，則G無割邊。極大平面圖非極大平面圖極大平面圖(1)先證明G連通。若不然，G至少兩個連通分支。設(shè)G1與G2是G的任意兩個連通分支。4把G1畫在G2的外部面上，并在G1,G2上分別取一點u與v.連接u與v得到一個新平面圖G*。但這與G是極大平面圖相矛盾。(2)當(dāng)G的階數(shù)n≥3時，我們證明G中沒有割邊。若不然，設(shè)G中有割邊e=uv，則G-uv不

3、連通，恰有兩個連通分支G1與G2。uveG1G2Gf5設(shè)u在G1中，而v在G2中。由于n≥3,所以，至少有一個分支包含兩個以上的頂點。設(shè)G2至少含有兩個頂點。又設(shè)G1中含有點u的面是f,將G2畫在f內(nèi)。由于G是單圖，所以，在G2的外部面上存在不等于點v的點t?，F(xiàn)在，在G中連接點u與t得新平面圖G*,它比G多一條邊。這與G的極大性相矛盾。vueG1G2G6下面證明極大平面圖的一個重要性質(zhì)。定理1設(shè)G是至少有3個頂點的平面圖，則G是極大平面圖，當(dāng)且僅當(dāng)G的每個面的次數(shù)是3且為單圖。注：該定理可以簡單記

4、為是“極大平面圖的三角形特征”，即每個面的邊界是三角形。證明：“必要性”由引理知，G是單圖、G無割邊。于是G的每個面的次數(shù)至少是3。假設(shè)G中某個面f的次數(shù)大于等于4。記f的邊界是v1v2v3v4…vk。如下圖所示:7如果v1與v3不鄰接，則連接v1v3，沒有破壞G的平面性，這與G是極大平面圖矛盾。所以v1v3必須鄰接，但必須在f外連線；同理v2與v4也必須在f外連線。但邊v1v3與邊v2v4在f外交叉，與G是平面圖矛盾！所以，G的每個面次數(shù)一定是3.定理的充分性是顯然的。v1v2v3v4v5vkf

5、8推論：設(shè)G是n個點，m條邊和ф?zhèn)€面的極大平面圖，且n≥3.則：(1)m=3n-6;(2)ф=2n-4.證明：因為G是極大平面圖，所以，每個面的次數(shù)為3.由次數(shù)公式：由歐拉公式：所以得：9所以得：又所以：注：頂點數(shù)相同的極大平面圖并不唯一。例如：正20面體非正20面體10還在研究中的問題是：頂點數(shù)相同的極大平面圖的個數(shù)和結(jié)構(gòu)問題。2、極大外平面圖及其性質(zhì)定義2若一個可平面圖G存在一種平面嵌入，使得其所有頂點均在某個面的邊界上，稱該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱為外平面圖。外可平面圖

6、外平面圖1f外平面圖2f11注：對外可平面圖G來說，一定存在一種外平面嵌入，使得G的頂點均在外部面的邊界上。這由球極投影法可以說明。下面研究極大外平面圖的性質(zhì)。定義3設(shè)G是一個簡單外可平面圖，若在G中任意不鄰接頂點間添上一條邊后，G成為非外可平面圖，則稱G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱為極大外平面圖。極大外平面圖12定理2設(shè)G是一個有n(n≥3)個點，且所有點均在外部面上的極大外平面圖，則G有n-2個內(nèi)部面。證明：對G的階數(shù)作數(shù)學(xué)歸納。當(dāng)n=3時，G是三角形，顯然只有一個內(nèi)部面；

7、設(shè)當(dāng)n=k時，結(jié)論成立。當(dāng)n=k+1時，首先，注意到G必有一個2度頂點u在G的外部面上。(這可以由上面引理得到)考慮G1=G-v。由歸納假設(shè)，G1有k-2個內(nèi)部面。這樣G有k-1個內(nèi)部面。于是定理2得證。引理設(shè)G是一個連通簡單外可平面圖，則在G中有一個度數(shù)至多是2的頂點。13定理3設(shè)G是一個有n(n≥3)個點，且所有點均在外部面上的外平面圖，則G是極大外平面圖，當(dāng)且僅當(dāng)其外部面的邊界是圈，內(nèi)部面是三角形。注：這是極大外平面圖的典型特征。證明：先證明必要性。(1)證明G的邊界是圈。容易知道：G的外部

8、面邊界一定為閉跡，否則，G不能為極大外平面圖。設(shè)W=v1v2…vnv1是G的外部面邊界。若W不是圈，則存在i與j,使vi=vj=v.此時，G可以示意如下：Wvi-1v1vnv2vi+1vj-1vj+1v14vi-1與vi+1不能鄰接。否則W不能構(gòu)成G的外部面邊界。這樣，我們連接vi-1與vi+1：vi-1v1vnv2vi+1vj-1vj+1v得到一個新外平面圖。這與G的極大性矛盾。(2)證明G的內(nèi)部面是三角形。首先，注意到，G的內(nèi)部面必須是圈。因為，G的外部面的邊界是生成圈，所以G