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

1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、一些特殊平面圖,(二)、平面圖的對(duì)偶圖,特殊平面圖與平面圖的對(duì)偶圖,1、極大平面圖及其性質(zhì),2、極大外平面圖及其性質(zhì),3,1、極大平面圖及其性質(zhì),(一)、一些特殊平面圖,對(duì)于一個(gè)簡(jiǎn)單平面圖來說，在不鄰接頂點(diǎn)對(duì)間加邊，當(dāng)邊數(shù)增加到一定數(shù)量時(shí)，就會(huì)變成非平面圖。這樣，就啟發(fā)我們研究平面圖的極圖問題。,定義1 設(shè)G是簡(jiǎn)單可平面圖，如果G是Ki (1i4),或者在G的任意非鄰接頂點(diǎn)間添加一條邊后，得到的圖均是非可平面圖，則稱G是極大可平面圖。,極大可平面圖的平面嵌入稱為極大平面圖。,4,注：只有在單圖前提下才能定義極大平面圖。,引理 設(shè)G是極大平面圖，則G必然連通；若G的階數(shù)大于等于3，則G無割邊。,(1) 先證明G連通。,若不然，G至少兩個(gè)連通分支。設(shè)G1與G2是G的任意兩個(gè)連通分支。,5,把G1畫在G2的外部面上，并在G1,G2上分別取一點(diǎn)u與v.連接u與v得到一個(gè)新平面圖G*。但這與G是極大平面圖相矛盾。,(2) 當(dāng)G的階數(shù)n3時(shí)，我們證明G中沒有割邊。,若不然，設(shè)G中有割邊e = uv，則G-uv不連通，恰有兩個(gè)連通分支G1與G2。,6,設(shè)u在G1中，而v在G2中。由于n3, 所以，至少有一個(gè)分支包含兩個(gè)以上的頂點(diǎn)。設(shè)G2至少含有兩個(gè)頂點(diǎn)。又設(shè)G1中含有點(diǎn)u的面是 f , 將G2畫在 f 內(nèi)。,由于G是單圖，所以，在G2的外部面上存在不等于點(diǎn)v的點(diǎn)t?，F(xiàn)在，在G中連接點(diǎn)u與t得新平面圖G*,它比G多一條邊。這與G的極大性相矛盾。,7,下面證明極大平面圖的一個(gè)重要性質(zhì)。,定理1 設(shè)G是至少有3個(gè)頂點(diǎn)的平面圖，則G是極大平面圖，當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)是3且為單圖。,注：該定理可以簡(jiǎn)單記為是“極大平面圖的三角形特征”，即每個(gè)面的邊界是三角形。,證明：“必要性”,由引理知，G是單圖、G無割邊。于是G的每個(gè)面的次數(shù)至少是3。,假設(shè)G中某個(gè)面 f 的次數(shù)大于等于4。記 f 的邊界是v1v2v3v4vk。如下圖所示:,8,如果v1與v3不鄰接，則連接v1v3，沒有破壞G的平面性，這與G是極大平面圖矛盾。所以v1v3必須鄰接，但必須在 f 外連線；同理v2與v4也必須在 f 外連線。但邊v1v3與邊v2v4在 f 外交叉，與G是平面圖矛盾！,所以，G的每個(gè)面次數(shù)一定是3.,定理的充分性是顯然的。,9,推論：設(shè)G是n個(gè)點(diǎn)，m條邊和個(gè)面的極大平面圖，且n3.則：(1) m=3n-6; (2) =2n-4.,證明：因?yàn)镚是極大平面圖，所以，每個(gè)面的次數(shù)為3.由次數(shù)公式：,由歐拉公式：,所以得：,10,所以得：,又,所以：,注：頂點(diǎn)數(shù)相同的極大平面圖并不唯一。例如：,11,還在研究中的問題是：頂點(diǎn)數(shù)相同的極大平面圖的個(gè)數(shù)和結(jié)構(gòu)問題。,2、極大外平面圖及其性質(zhì),定義2 若一個(gè)可平面圖G存在一種平面嵌入，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱為外平面圖。,12,注：對(duì)外可平面圖G來說，一定存在一種外平面嵌入，使得G的頂點(diǎn)均在外部面的邊界上。這由球極投影法可以說明。,下面研究極大外平面圖的性質(zhì)。,定義3 設(shè)G是一個(gè)簡(jiǎn)單外可平面圖，若在G中任意不鄰接頂點(diǎn)間添上一條邊后，G成為非外可平面圖，則稱G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱為極大外平面圖。,13,定理2 設(shè)G是一個(gè)有n (n3)個(gè)點(diǎn)，且所有點(diǎn)均在外部面上的極大外平面圖，則G有n-2個(gè)內(nèi)部面。,證明：對(duì)G的階數(shù)作數(shù)學(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)。,14,定理3 設(shè)G是一個(gè)有n (n3)個(gè)點(diǎn)，且所有點(diǎn)均在外部面上的外平面圖，則G是極大外平面圖，當(dāng)且僅當(dāng)其外部面的邊界是圈，內(nèi)部面是三角形。,注：這是極大外平面圖的典型特征。,證明：先證明必要性。,(1) 證明G的邊界是圈。,容易知道：G的外部面邊界一定為閉跡，否則，G不能為極大外平面圖。設(shè)W=v1v2vnv1是G的外部面邊界。若W不是圈，則存在i與j, 使vi=vj=v.此時(shí)，G可以示意如下：,15,vi-1與vi+1不能鄰接。否則W不能構(gòu)成G的外部面邊界。這樣，我們連接vi-1與vi+1：,得到一個(gè)新外平面圖。這與G的極大性矛盾。,(2) 證明G的內(nèi)部面是三角形。,首先，注意到，G的內(nèi)部面必須是圈。因?yàn)?，G的外部面的邊界是生成圈，所以G是2連通的，所以，G的每個(gè)面的邊界必是圈。,16,其次，設(shè)C是G中任意一個(gè)內(nèi)部面的邊界。如果C的長(zhǎng)度大于等于4，則C中一定存在不鄰接頂點(diǎn)，連接這兩點(diǎn)得到一個(gè)新平面圖，這與G的極大性矛盾。又由于G是單圖，所以C的長(zhǎng)度只能為3.,下面證明充分性。,設(shè)G是一個(gè)外平面圖，內(nèi)部面是三角形，外部面是圈W.,如果G不是極大外平面圖，那么存在不鄰接頂點(diǎn)u與v,使得G+uv是外平面圖。,但是，G+uv不能是外平面圖。因?yàn)?，若邊uv經(jīng)過W的內(nèi)部，則它要與G的其它邊相交；若uv經(jīng)過W的外部，導(dǎo)致所有點(diǎn)不能在G的同一個(gè)面上。,所以，G是極大外平面圖。,17,定理4 每個(gè)至少有7個(gè)頂點(diǎn)的外可平面圖的補(bǔ)圖不是外可平面圖，且7是這個(gè)數(shù)目的最小者。,我們用枚舉方法證明。,證明：對(duì)于n=7的極大外可平面圖來說，只有4個(gè)。如下圖所示。,直接驗(yàn)證：它們的補(bǔ)圖均不是外可平面的。,而當(dāng)n=6時(shí)，我們可以找到一個(gè)外可平面圖G(見下圖),使得其補(bǔ)圖是外可平面圖。,18,(二)、平面圖的對(duì)偶圖,1、對(duì)偶圖的定義,定義4 給定平面圖G，G的對(duì)偶圖G*如下構(gòu)造：,(1) 在G的每個(gè)面fi內(nèi)取一個(gè)點(diǎn)vi*作為G*的一個(gè)頂點(diǎn)；,(2) 對(duì)G的一條邊e, 若e是面 fi 與 fj 的公共邊，則連接vi*與vj*，且連線穿過邊e;若e是面 fi 中的割邊，則以vi為頂點(diǎn),19,作環(huán)，且讓它與e相交。,例如，作出平面圖G的對(duì)偶圖G*,20,2、對(duì)偶圖的性質(zhì),(1)、G與G*的對(duì)應(yīng)關(guān)系,1) G*的頂點(diǎn)數(shù)等于G的面數(shù)；,2) G*的邊數(shù)等于G的邊數(shù)；,3) G*的面數(shù)等于G的頂點(diǎn)數(shù)；,4) d (v*)=deg( f ),21,(2)、定理5,定理5 平面圖G的對(duì)偶圖必然連通,證明：在G*中任意取兩點(diǎn)vi*與vj*。我們證明該兩點(diǎn)連通即可！,用一條曲線 l 把vi*和vj*連接起來，且 l 不與G*的任意頂點(diǎn)相交。,顯然，曲線 l 從vi*到vj*經(jīng)過的面邊序列，對(duì)應(yīng)從vi*到vj*的點(diǎn)邊序列，該點(diǎn)邊序列就是該兩點(diǎn)在G*中的通路。,注: (1) 由定理5知：(G*)*不一定等于G;,22,證明：“必要性”,(2) G是平面圖，則 當(dāng)且僅當(dāng)G是連通的。(習(xí)題第26題),由于G是平面圖，由定理5，G*是連通的。而由G*是平面圖，再由定理5，(G*)*是連通的。,所以，由 得：G是連通的。,“充分性”,由對(duì)偶圖的定義知，平面圖G與其對(duì)偶圖G*嵌入在同一平面上，當(dāng)G連通時(shí)，容易知道：G*的無界面 f *中僅含G的唯一頂點(diǎn)v,而除v外，G中其它頂點(diǎn)u均與G*的有限面形成一一對(duì)應(yīng)，于是，G中頂點(diǎn)和G*頂點(diǎn)在這種自然對(duì)應(yīng)方式下一一對(duì)應(yīng)，且對(duì)應(yīng)頂點(diǎn)間鄰接關(guān)系保持不變，故：,23,(3) 同構(gòu)的平面圖可以有不同構(gòu)的對(duì)偶圖。,例如，下面的兩個(gè)圖：,但,這是因?yàn)椋篏2中有次數(shù)是1的面，而G1沒有次數(shù)是1的面。所以，它們的對(duì)偶圖不能同構(gòu)。,24,第一次上交作業(yè),第3章 習(xí)題3 ：1，7，9，16.,第4章 習(xí)題4 ：3，7，10，12.,第5章 習(xí)題5 ：1，2，6，7，13，19。,25,作業(yè),P143-146 習(xí)題5 ：3，4，5，6，8， 25, 26，27。,其中 25，26，27結(jié)合課件學(xué)習(xí)。,26,Thank You !,27,例2 證明：,(1) B是平面圖G的極小邊割集，當(dāng)且僅當(dāng),是G*的圈。,(2) 歐拉平面圖的對(duì)偶圖是偶圖。,28,證明: (1),對(duì)B的邊數(shù)作數(shù)學(xué)歸納。,當(dāng)B的邊數(shù)n=1時(shí)，B中邊是割邊,顯然，在G*中對(duì)應(yīng)環(huán)。所以，結(jié)論成立。,設(shè)對(duì)B的邊數(shù)nk 時(shí)，結(jié)論成立?？紤]n=k的情形。,設(shè)c1 B, 于是B-c1是G-c1=G1的一個(gè)極小邊割集。由歸納假設(shè)：,是G1*的一個(gè)圈。且圈C1*上的頂點(diǎn)對(duì)應(yīng)于G1中的面f, f 的邊界上有極小邊割集B-e1的邊。,29,現(xiàn)在，把e1加入到G1中，恢復(fù)G。,由于G是平面圖，其作用相當(dāng)于圈C1*上的一個(gè)頂點(diǎn)對(duì)應(yīng)于G1中的一個(gè)平面區(qū)域 f, 被e1劃分成兩個(gè)頂點(diǎn)f1*與f2*,并在其間連以e1所對(duì)應(yīng)的邊e1*。,所以，B對(duì)應(yīng)在G*中的C*仍然是一個(gè)圈。由歸納法，結(jié)論得到證明。,30,充分性：,G*中的一個(gè)圈，對(duì)應(yīng)于G中,的邊的集合B顯然是G中的一個(gè)邊割集。,若該割集不是極小邊割集，則它是G中極小邊割集之和。而由必要性知道：每個(gè)極小邊割集對(duì)應(yīng)G*的一個(gè)圈，于是推出B在G*中對(duì)應(yīng)的邊集合是圈之并。但這與假設(shè)矛盾。,(2) 因歐拉圖的任意邊割集均有偶數(shù)條邊。于是由(1),G*中不含奇圈。所以G*是偶圖。,31,例3 設(shè)T是連通平面圖G的生成樹，,證明：T*=G*E*是G*中的生成樹。(習(xí)題第27題),32,證明：情形1，如果G是樹。,在這種情況下，E* = .則T*是平凡圖，而G*的生成樹也是平凡圖，所以，結(jié)論成立；,情形2，如果G不是樹。,因G的每個(gè)面必然含有邊e不