《圖論課件-特殊平面圖與平面圖的對偶.ppt》由會員分享，可在線閱讀，更多相關(guān)《圖論課件-特殊平面圖與平面圖的對偶.ppt（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

4、 外連線；同理v2與v4也必須在f外連線。但邊v1v3與邊v2v4在 f 外交叉，與G是平面圖矛盾！,所以，G的每個面次數(shù)一定是3.,定理的充分性是顯然的。,8,推論：設(shè)G是n個點，m條邊和個面的極大平面圖，且n3.則：(1) m=3n-6; (2) =2n-4.,證明：因為G是極大平面圖，所以，每個面的次數(shù)為3.由次數(shù)公式：,由歐拉公式：,所以得：,9,所以得：,又,所以：,注：頂點數(shù)相同的極大平面圖并不唯一。例如：,10,還在研究中的問題是：頂點數(shù)相同的極大平面圖的個數(shù)和結(jié)構(gòu)問題。,2、極大外平面圖及其性質(zhì),與極大平面圖相對應(yīng)的圖是極小平面圖。,定義2 若一個可平面圖G存在一種平面嵌入，使

5、得其所有頂點均在某個面的邊界上，稱該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱為外平面圖。,11,注：對外可平面圖G來說，一定存在一種外平面嵌入，使得G的頂點均在外部面的邊界上。這由球極投影法可以說明。,下面研究極大外平面圖的性質(zhì)。,定義3 設(shè)G是一個簡單外可平面圖，若在G中任意不鄰接頂點間添上一條邊后，G成為非外可平面圖，則稱G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱為極大外平面圖。,12,引理 設(shè)G是一個連通簡單外可平面圖，則在G中有一個度數(shù)至多是2的頂點。,證明 我們對G的階數(shù)n作數(shù)學(xué)歸納。,當(dāng)n3時，引理結(jié)論顯然成立；當(dāng)n=4時，由于K4不能是外可平面圖，所以，四階的外可平

6、面圖至少有一個頂點度數(shù)不超過2。事實上，更強一點的結(jié)論是：當(dāng)n=4時，有兩個不鄰接頂點，其度數(shù)不超過2.,設(shè)當(dāng)G是一個階數(shù)小于n的簡單連通外可平面圖時，存在兩個不鄰接頂點，其度數(shù)不超過2。,考慮G是一個階數(shù)等于n的簡單連通外可平面圖。,情形1，如果G有割點x,13,由歸納假設(shè)，G-x的兩個不同分支中分別有一個異于x的頂點z與z1,使得度數(shù)不超過2。這說明G中有兩個不鄰接頂點, 使得度數(shù)都不超過2；,情形2 若G是2連通的。,考慮G的任意一種外平面嵌入。則G的外部面邊界一定是圈。否則，容易推出G有割點。,設(shè)C是G的外平面嵌入的外部面邊界。若除C外，圖中沒有其它的邊，則G=C, 顯然G中有不鄰接點

7、，度數(shù)不超過2；,14,若除C外，圖中至少有邊xy。如下圖所示：,則在C上的兩條xy路上的點在G中的兩個導(dǎo)出子圖H1與H2是外平面圖。,有歸納假設(shè)，在H1,H2中分別存在異于x ,y的點z與z1,使得，它們的度數(shù)不超過2.,15,定理2 設(shè)G是一個有n (n3)個點，且所有點均在外部面上的極大外平面圖，則G有n-2個內(nèi)部面。,證明：對G的階數(shù)作數(shù)學(xué)歸納。,當(dāng)n=3時，G是三角形，顯然只有一個內(nèi)部面；,設(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)部面。于是

8、定理2得證。,16,定理3 設(shè)G是一個有n (n3)個點，且所有點均在外部面上的外平面圖，則G是極大外平面圖，當(dāng)且僅當(dāng)其外部面的邊界是圈，內(nèi)部面是三角形。,注：這是極大外平面圖的典型特征。,證明：先證明必要性。,(1) 證明G的邊界是圈。,設(shè)W=v1v2vnv1是G的外部面邊界。若W不是圈，則存在i與j,使得：1i,jn,且j-i1(modn),使vi=vj=v.此時，G可以示意如下：,17,vi-1與vi+1不能鄰接。否則W不能構(gòu)成G的外部面邊界。這樣，我們連接vi-1與vi+1：,得到一個新外平面圖。這與G的極大性矛盾。,(2) 證明G的內(nèi)部面是三角形。,首先，注意到，G的內(nèi)部面必須是圈。

9、因為，G的外部面的邊界是生成圈，所以G是2連通的，所以，G的每個面的邊界必是圈。,18,其次，設(shè)C是G中任意一個內(nèi)部面的邊界。如果C的長度大于等于4，則C中一定存在不鄰接頂點，連接這兩點得到一個新平面圖，這與G的極大性矛盾。又由于G是單圖，所以C的長度只能為3.,下面證明充分性。,設(shè)G是一個外平面圖，內(nèi)部面是三角形，外部面是圈W.,如果G不是極大外平面圖，那么存在不鄰接頂點u與v,使得G+uv是外平面圖。,但是，G+uv不能是外平面圖。因為，若邊uv經(jīng)過W的內(nèi)部，則它要與G的其它邊相交；若uv經(jīng)過W的外部，導(dǎo)致所有點不能在在G的同一個面上。,所以，G是極大外平面圖。,19,定理4 每個至少有7

10、個頂點的外可平面圖的補圖不是外可平面圖，且7是這個數(shù)目的最小者。,我們用枚舉方法證明。,證明：對于n=7的極大外可平面圖來說，只有4個。如下圖所示。,直接驗證：它們的補圖均不是外可平面的。,而當(dāng)n=6時，我們可以找到一個外可平面圖G(見下圖),使得其補圖是外可平面圖。,20,(二)、平面圖的對偶圖,1、對偶圖的定義,定義4 給定平面圖G，G的對偶圖G*如下構(gòu)造：,(1) 在G的每個面fi內(nèi)取一個點vi*作為G*的一個頂點；,(2) 對G的一條邊e, 若e是面 fi 與 fj 的公共邊，則連接vi*與vj*，且連線穿過邊e;若e是面fi中的割邊，則以vi為頂點,21,作環(huán)，且讓它與e相交。,例如

11、，作出平面圖G的對偶圖G*,22,2、對偶圖的性質(zhì),(1)、G與G*的對應(yīng)關(guān)系,1) G*的頂點數(shù)等于G的面數(shù)；,2) G*的邊數(shù)等于G的邊數(shù)；,3) G*的面數(shù)等于G的頂點數(shù)；,4) d (v*)=deg( f ),23,(2)、定理5,定理5 平面圖G的對偶圖必然連通,證明：在G*中任意取兩點vi*與vj*。我們證明該兩點連通即可！,用一條曲線 l 把vi*和vj*連接起來，且 l 不與G*的任意頂點相交。,顯然，曲線 l 從vi*到vj*經(jīng)過的面邊序列，對應(yīng)從vi*到vj*的點邊序列，該點邊序列就是該兩點在G*中的通路。,注: (1) 由定理5知：(G*)*不一定等于G;,24,證明：“

12、必要性”,(2) G是平面圖，則 當(dāng)且僅當(dāng)G是連通的。(習(xí)題第26題),由于G是平面圖，由定理5，G*是連通的。而由G*是平面圖，再由定理5，(G*)*是連通的。,所以，由 得：G是連通的。,“充分性”,由對偶圖的定義知，平面圖G與其對偶圖G*嵌入在同一平面上，當(dāng)G連通時，容易知道：G*的無界面 f **中僅含G的唯一頂點v,而除v外，G中其它頂點u均與G*的有限面形成一一對應(yīng)，且對應(yīng)頂點間鄰接關(guān)系保持不變，即：,25,(3) 同構(gòu)的平面圖可以有不同構(gòu)的對偶圖。,例如，下面的兩個圖：,但,這是因為：G2中有次數(shù)是1的面，而G1沒有次數(shù)是1的面。所以，它們的對偶圖不能同構(gòu)。,

13、26,例2 證明：,(1) B是平面圖G的極小邊割集，當(dāng)且僅當(dāng),是G*的圈。,(2) 歐拉平面圖的對偶圖是偶圖。,27,證明: (1),對B的邊數(shù)作數(shù)學(xué)歸納。,當(dāng)B的邊數(shù)n=1時，B中邊是割邊,顯然，在G*中對應(yīng)環(huán)。所以，結(jié)論成立。,設(shè)對B的邊數(shù)n

14、頂點f1*與f2*,并在其間連以e1所對應(yīng)的邊e1*。,所以，B對應(yīng)在G*中的C*仍然是一個圈。由歸納法，結(jié)論得到證明。,29,充分性：,G*中的一個圈，對應(yīng)于G中,的邊的集合B顯然是G中的一個邊割集。,若該割集不是極小邊割集，則它是G中極小邊割集之和。而由必要性知道：每個極小邊割集對應(yīng)G*的一個圈，于是推出B在G*中對應(yīng)的邊集合是圈之并。但這與假設(shè)矛盾。,(2) 因歐拉圖的任意邊割集均有偶數(shù)條邊。于是由(1),G*中不含奇圈。所以G*是偶圖。,30,例3 設(shè)T是連通平面圖G的生成樹，,證明：T*=G*E*是G*中的生成樹。(習(xí)題第27題),31,證明：情形1，如果G是樹。,在這種情況下，E*

15、 = .則T*是平凡圖，而G*的生成樹也是平凡圖，所以，結(jié)論成立；,情形2，如果G不是樹。,因G的每個面必然含有邊e不屬于E(T),即G*的每個頂點必然和E*中的某邊關(guān)聯(lián)，于是T*必然是G*的生成子圖。,下面證明：T*中沒有圈。,若T*中有圈。則由例2知：T的余樹中含有G的極小邊割集。但我們又可以證明：如果T是連通圖G的生成樹，那么，T的余樹不含G的極小邊割集。這樣，T*不能含G*的圈。,32,又因在G中，每去掉T的余樹中的一條邊，G的面減少一個，當(dāng)T的余樹中的邊全去掉時，G變成一顆樹T.,于是，有：,所以，T*是G*的生成樹。,33,作業(yè),P143---146 習(xí)題5 ：3，4，5，6，8， 25, 26，27。,其中 25，26，27結(jié)合課件學(xué)習(xí)。,34,Thank You !,