ppt特殊平面圖與平面圖的對(duì)偶

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

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

2、義極大平面圖。引理設(shè)G是極大平面圖，則G必然連通；若G的階數(shù)大于等于3，則G無(wú)割邊。極大平面圖非極大平面圖極大平面圖(1)先證明G連通。若不然，G至少兩個(gè)連通分支。設(shè)G1與G2是G的任意兩個(gè)連通分支。4把G1畫(huà)在G2的外部面上，并在G1,G2上分別取一點(diǎn)u與v.連接u與v得到一個(gè)新平面圖G*。但這與G是極大平面圖相矛盾。(2)當(dāng)G的階數(shù)n≥3時(shí)，我們證明G中沒(méi)有割邊。若不然，設(shè)G中有割邊e=uv，則G-uv不連通，恰有兩個(gè)連通分支G1與G2。uveG1G2Gf5設(shè)u在G1中，而v在G2中。由于n≥3,所以，至少有一個(gè)分支包含兩個(gè)以上的頂點(diǎn)。設(shè)G2至少含有兩個(gè)頂點(diǎn)。又設(shè)G1中含有點(diǎn)u的面

3、是f,將G2畫(huà)在f內(nèi)。由于G是單圖，所以，在G2的外部面上存在不等于點(diǎn)v的點(diǎn)t?，F(xiàn)在，在G中連接點(diǎn)u與t得新平面圖G*,它比G多一條邊。這與G的極大性相矛盾。vueG1G2G6下面證明極大平面圖的一個(gè)重要性質(zhì)。定理1設(shè)G是至少有3個(gè)頂點(diǎn)的平面圖，則G是極大平面圖，當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)是3且為單圖。注：該定理可以簡(jiǎn)單記為是“極大平面圖的三角形特征”，即每個(gè)面的邊界是三角形。證明：“必要性”由引理知，G是單圖、G無(wú)割邊。于是G的每個(gè)面的次數(shù)至少是3。假設(shè)G中某個(gè)面f的次數(shù)大于等于4。記f的邊界是v1v2v3v4…vk。如下圖所示:7如果v1與v3不鄰接，則連接v1v3，沒(méi)有破壞G的平面

4、性，這與G是極大平面圖矛盾。所以v1v3必須鄰接，但必須在f外連線(xiàn)；同理v2與v4也必須在f外連線(xiàn)。但邊v1v3與邊v2v4在f外交叉，與G是平面圖矛盾！所以，G的每個(gè)面次數(shù)一定是3.定理的充分性是顯然的。v1v2v3v4v5vkf8推論：設(shè)G是n個(gè)點(diǎn)，m條邊和ф?zhèn)€面的極大平面圖，且n≥3.則：(1)m=3n-6;(2)ф=2n-4.證明：因?yàn)镚是極大平面圖，所以，每個(gè)面的次數(shù)為3.由次數(shù)公式：由歐拉公式：所以得：9所以得：又所以：注：頂點(diǎn)數(shù)相同的極大平面圖并不唯一。例如：正20面體非正20面體10還在研究中的問(wèn)題是：頂點(diǎn)數(shù)相同的極大平面圖的個(gè)數(shù)和結(jié)構(gòu)問(wèn)題。2、極大外平面圖及其性質(zhì)定義

5、2若一個(gè)可平面圖G存在一種平面嵌入，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱(chēng)該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱(chēng)為外平面圖。外可平面圖外平面圖1f外平面圖2f11注：對(duì)外可平面圖G來(lái)說(shuō)，一定存在一種外平面嵌入，使得G的頂點(diǎn)均在外部面的邊界上。這由球極投影法可以說(shuō)明。下面研究極大外平面圖的性質(zhì)。定義3設(shè)G是一個(gè)簡(jiǎn)單外可平面圖，若在G中任意不鄰接頂點(diǎn)間添上一條邊后，G成為非外可平面圖，則稱(chēng)G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱(chēng)為極大外平面圖。極大外平面圖12定理2設(shè)G是一個(gè)有n(n≥3)個(gè)點(diǎn)，且所有點(diǎn)均在外部面上的極大外平面圖，則G有n-2個(gè)內(nèi)部面。證明：對(duì)G的階數(shù)作數(shù)

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

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