ppt23平面性算法平面性判定方法.ppt

1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、涉及算法的相關(guān)概念,(二)、平面性算法,平面性算法,3,關(guān)于圖的平面性問(wèn)題，我們已經(jīng)建立了一些平面性判定方法：,(一)、涉及算法的相關(guān)概念,(1) 對(duì)于簡(jiǎn)單圖G=(n, m)，如果m3n-6，則G是非可平面的；,(2) 對(duì)于連通圖G=(n, m)，如果每個(gè)面次數(shù)至少為l3,且m(n-2)l /(l-2)，則G是非可平面的；,(3) 庫(kù)拉托斯基定理：G是可平面的當(dāng)且僅當(dāng)G不含有與K5或K3,3同胚的子圖；,(4) 瓦格納定理：G是可平面的當(dāng)且僅當(dāng)G不含有能夠收縮成K5或K3,3的子圖；,4,上面的判定方法，局限性很大。這次課我們將給出一個(gè)算法，其作用是：如果G非可平面，通過(guò)算法可以得到判定；如果G是可平面圖，通過(guò)算法，可以給出一種平面嵌入形式。,定義1 設(shè)H是G的一個(gè)子圖，在E(G)-E(H)中定義一個(gè)二元關(guān)系“ ”:,(1) e1與e2分別是W的始邊和終邊，且,(2) W的內(nèi)點(diǎn)與H不能相交。,5,定義2 設(shè)B是E(G)-E(H)關(guān)于二元關(guān)系“ ” 的等價(jià)類在G中的邊導(dǎo)出子圖，則稱B是G關(guān)于子圖H的一座橋。橋與H的公共頂點(diǎn)稱為橋B在H中的附著頂點(diǎn)。,例1 在下圖中，紅色邊在G中導(dǎo)出子圖為H。求出G關(guān)于H的所有橋。,6,定義3 設(shè)H是圖G的可平面子圖， 是H的一種平面嵌入。若G也是可平面圖，且存在G的一個(gè)平面嵌入 ，使得：,稱 是G容許的。,例2 在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H, 并取,容易知道： 是G容許的。,7,例3 在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H, 并取,容易知道： 不 是G容許的。,定義4 設(shè)B是G中子圖H的任意一座橋，若B對(duì)H的所有附著頂點(diǎn)都位于 的某個(gè)面 f 的邊界上，則稱B在面 f 內(nèi)可畫(huà)入，否則，稱B在面 f 內(nèi)不可畫(huà)入。,8,對(duì)于G的橋B,令：,例4 紅色邊的導(dǎo)出子圖是H,如果取 確定H的橋在 中可以畫(huà)入的面集合。,解：,9,定理1 設(shè) 是G容許的，則對(duì)于H的每座橋B:,證明：因 是G容許的，由定義，存在G的一個(gè)平面嵌入 ，使得：,于是，H的橋B所對(duì)應(yīng)的 的子圖，必然限制在 的某個(gè)面內(nèi)。所以：,注：定理1實(shí)際上給出了一個(gè)圖是可平面圖的一個(gè)必要條件。這個(gè)必要條件表明：如果存在G的一個(gè)可平面子圖H,10,使得對(duì)于某橋B，有 ，那么，G是非可平面的。,根據(jù)上面的結(jié)論：我們可以按如下方式來(lái)考慮G的平面性問(wèn)題：,先取G的一個(gè)可平面子圖H1, 其平面嵌入是,對(duì)于H1的每座橋B,如果： ，則G非可平面。,否則，取H1的橋B1,作：H2=B1H1,再取一個(gè)面,將B1畫(huà)入 的面 f 中。,11,如果B1可平面，則只要把B1平面嵌入后，得到H2的平面嵌入,然后再進(jìn)行上面相同的操作，可以得到G的邊數(shù)遞增的子圖平面嵌入序列：,最終，得到可平面圖G的一種平面嵌入形式。,(二)、平面性算法,1964年，Demoucron, Mlgrance和Pertuiset提出了下面的平面性算法，簡(jiǎn)稱DMP算法。,12,設(shè)G是至少三個(gè)頂點(diǎn)的簡(jiǎn)單塊。,(1) 取G的一個(gè)圈H1,求出H1的一個(gè)平面嵌入 。置i=1;,(2) 若E(G)-E(Hi)=,則停止；否則，確定G中Hi的所有橋，并對(duì)每座橋B，求出 ；,(3) 若存在橋B,使得： ，則停止 (G不可平面) ；否則，在Hi的所有橋中確定一個(gè)使得 最小的B，并取 。,(4) 在橋B中取一條連接Hi中兩個(gè)附著頂點(diǎn)的路Pi,置Hi+1=HiPi,把Pi畫(huà)在 的面 f 內(nèi),得到,13,(5) 置i=i+1轉(zhuǎn)(2)。,例5 用平面性算法考察下圖G的平面性。,解：(1) 取G的一個(gè)圈H1,并作平面嵌入：,14,(2),15,(3) 取B1和f1. (4) 取P1=v1v3,16,(3) 取B2和f3. (4) 取P2=v2v7,17,18,(3) 取B1和f1. (4) 取P3=v1v4,19,(3) 取B1和f5. (4) 取P4=v2v6,20,繼續(xù)下去，得到：,算法分析：主要運(yùn)算包括：,21,（i）找出塊G中的一個(gè)圈Hi；,（ii）確定G中Hi的橋以及它們對(duì)于Hi的附著點(diǎn)；,（iii）對(duì)于 的每個(gè)面 f 確定其周界；,（iv）對(duì)于 的每座橋B，確定,（v）在Hi 的某座橋B中求一條起點(diǎn)與終點(diǎn)均為附著點(diǎn) 的一條路Pi。,可證上述每一個(gè)算法均存在好算法，因此平面性算法 也是好算法。,本章部分習(xí)題解答,22,例1 求證，每個(gè)5連通簡(jiǎn)單可平面圖至少有12個(gè)頂點(diǎn)。,證明：設(shè)G是5連通圖，則：,由惠特尼定理得：,所以：,另一方面：G是5連通簡(jiǎn)單可平面圖，所以有：,于是得：,即：,所以：n12。,23,例2 求證，沒(méi)有6連通簡(jiǎn)單可平面圖。,證明：若不然，設(shè)G是6連通圖，則：,由惠特尼定理得：,所以：,于是得：,這與G是簡(jiǎn)單平面圖矛盾。,例3 求證：若G是連通平面圖，且所有頂點(diǎn)度數(shù)不小于3，則G至少有一個(gè)面 f，使得：deg ( f ) 5。,24,證明：若不然，則：,由歐拉公式得：,于是得：,另一方面：由(G)3得：2m3n 3n-6,這樣導(dǎo)出矛盾。,25,例4 設(shè)G是一個(gè)(n, m)單圖，圖G分解為可平面子圖的最少個(gè)數(shù)稱為G的厚度(G).求證：,(1),(2),26,證明: (1) 當(dāng)n=1時(shí)，結(jié)論成立。,設(shè)當(dāng)n3時(shí)，G分解為(G)個(gè)可平面子圖Gi(1i (G),因?yàn)槊總€(gè)Gi是平面單圖，于是：,所以：,27,(2) 根據(jù)完全圖的邊數(shù)和結(jié)論(1)，可得到(2)中不等式。又因?yàn)镵3, K4是平面圖，所以(K3)= (K4)=1，而直接計(jì)算：,所以，等式對(duì)n=3與4時(shí)也成立！當(dāng)5n8時(shí)，Kn是非可平面圖。因?yàn)榇嬖?階簡(jiǎn)單可平面圖G，其補(bǔ)圖也是可平面圖，所以對(duì)5n8，Kn可以分解為兩個(gè)可平面圖，