圖論課件-平面性算法

圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1本次課主要內(nèi)容(一)、涉及算法的相關(guān)概念(二)、平面性算法平面性算法2本次課主要內(nèi)容(一)、涉及算法的相關(guān)概念(二)、平面性算法平關(guān)于圖的平面性問題，我們建立了一些可平面性判定方法：(一)、涉及算法的相關(guān)概念

(1)對于簡單圖G=(n,m)，如果m>3n-6，則G是非可平面的；

(2)對于連通圖G=(n,m)，如果每個面次數(shù)至少為l≥3,且m>(n-2)l/(l-2)，則G是非可平面的；

(3)庫拉托斯基定理：G是可平面的當(dāng)且僅當(dāng)G不含有與K5或K3,3同胚的子圖；

(4)瓦格納定理：G是可平面的當(dāng)且僅當(dāng)G不含有能夠收縮成K5或K3,3的子圖；3關(guān)于圖的平面性問題，我們建立了一些可平面性判定方法上面的方法，局限性很大。這次課我們將給出一個算法，其作用是：如果G非可平面，通過算法可以得到判定；如果G是可平面圖，通過算法，可以給出一種平面嵌入形式。定義1設(shè)H是G的一個子圖，在E(G)-E(H)中定義一個二元關(guān)系“~”:

(1)e1與e2分別是W的始邊和終邊，且

(2)W與H的內(nèi)點(diǎn)不能相交。容易驗(yàn)證：上面的關(guān)系是E(G)-E(H)元間的等價(jià)關(guān)系。4上面的方法，局限性很大。這次課我們將給出一個算法，定義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的所有橋。GGB1B2B3B45定義2設(shè)B是E(G)-E(H)關(guān)于二元關(guān)系“~定義3設(shè)H是圖G的可平面子圖，是H的一種平面嵌入。若G也是可平面圖，且存在G的一個平面嵌入，且：稱是G容許的。例2在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取容易知道：是G容許的。G6定義3設(shè)H是圖G的可平面子圖，是H的一例3在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取容易知道：不是G容許的。定義4設(shè)B是G中子圖H的任意一座橋，若B對H的所有附著頂點(diǎn)都位于的某個面f的邊界上，則稱B在面f內(nèi)可畫入，否則，稱B在面f內(nèi)不可畫入。7例3在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取對于G的橋B,令：例4紅色邊的導(dǎo)出子圖是H,如果取確定H的橋在中可以畫入的面集合。B3B2B1f3f2f1G解：8對于G的橋B,令：例4紅色邊的導(dǎo)出子圖是H定理1設(shè)是G容許的，則對于H的每座橋B:證明：因是G容許的，由定義，存在G的一個平面嵌入，使得：于是，H的橋B所對應(yīng)的的子圖，必然限制在的某個面內(nèi)。所以：注：定理1實(shí)際上給出了一個圖是可平面圖的一個必要條件。這個必要條件表明：如果存在G的一個可平面子圖H,9定理1設(shè)是G容許的，則對于H的每使得對于某橋B，有，那么，G是非可平面的。根據(jù)上面的結(jié)論：我們可以按如下方式來考慮G的平面性問題：先取G的一個可平面子圖H1,其平面嵌入是對于H1的每座橋B,如果：，則G非可平面。否則，取H1的橋B1,作：H2=B1∪H1,再取一個面將B1畫入的面f中。10使得對于某橋B，有如果B1可平面，則只要把B1平面嵌入后，得到H2的平面嵌入然后再進(jìn)行上面相同的操作，可以得到G的邊數(shù)遞增的子圖平面嵌入序列：最終，得到可平面圖G的一種平面嵌入形式。(二)、平面性算法

1964年，Demoucron,Mlgrance和Pertuiset提出了下面的平面性算法，簡稱DMP算法。11如果B1可平面，則只要把B1平面嵌入后，得到H2的平設(shè)G是至少三個頂點(diǎn)的簡單塊。

(1)取G的一個圈H1,求出H1的一個平面嵌入。置i=1;

(2)若E(G)-E(Hi)=Φ,則停止；否則，確定G中Hi的所有橋，并對每座橋B，求出；

(3)若存在橋B,使得：，則停止(G不可平面)；否則，在Hi的所有橋中確定一個使得最小的B，并取。

(4)在橋B中取一條連接Hi中兩個附著頂點(diǎn)的路Pi,置Hi+1=Hi∪Pi,把Pi畫在的面f內(nèi),得到12設(shè)G是至少三個頂點(diǎn)的簡單塊。(1)取G的一

(5)置i=i+1轉(zhuǎn)(2)。例5用平面性算法考察下圖G的平面性。v6v5v4v3v2v1v8v7圖G解：(1)取G的一個圈H1,并作平面嵌入：13(5)置i=i+1轉(zhuǎn)(2)。例5用平面性v6v5v4v3v2v1v8v7圖G

(2)v6v5v4v3v2v1v8v7H1v6v5v4v3v2v1v8v7f1f214v6v5v4v3v2v1v8v7圖G(2)v6v5vv6v5v4v3v2v1v8v7圖G

(3)取B1和f1.(4)取P1=v1v3f3v6v5v4v3v2v1v8v7f1f215v6v5v4v3v2v1v8v7圖G(3)取B1和v6v5v4v3v2v1v8v7圖G

(3)取B2和f3.(4)取P2=v2v7v6v5v4v3v2v1v8v7f1f2f316v6v5v4v3v2v1v8v7圖G(3)取B2和v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1v8v7f1f2f3f417v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1

(3)取B1和f1.(4)取P3=v1v4v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1v8v7f1f2f3f5f418(3)取B1和f1.(4)取P3=v1vv6v5v4v3v2v1v8v7圖G

(3)取B1和f5.(4)取P4=v2v6v6v5v4v3v2v1v8v7f1f2f3f6f4f519v6v5v4v3v2v1v8v7圖G(3)取B1和v6v5v4v3v2v1v8v7圖G繼續(xù)下去，得到：v6v5v4v3v2v1v8v7算法分析：主要運(yùn)算包括：20v6v5v4v3v2v1v8v7圖G繼續(xù)下去，得到：（i）找出塊G中的一個圈Hi；（ii）確定G中Hi的橋以及它們對于Hi的附著點(diǎn)；（iii）對于的每個面f確定其周界；（iv）對于的每座橋B，確定（v）在Hi的某座橋B中求一條起點(diǎn)與終點(diǎn)均為附著點(diǎn)的一條路Pi。

可證上述每一個算法均存在好算法，因此平面性算法也是好算法。本章部分習(xí)題解答21（i）找出塊G中的一個圈Hi；（ii）確定G中Hi的橋以及它例1求證，每個5連通簡單可平面圖至少有12個頂點(diǎn)。證明：設(shè)G是5連通圖，則：由惠特尼定理得：所以：另一方面：G是5連通簡單可平面圖，所以有：于是得：即：所以：n≥12。22例1求證，每個5連通簡單可平面圖至少有12個頂點(diǎn)。例2求證，沒有6連通簡單可平面圖。證明：若不然，設(shè)G是6連通圖，則：由惠特尼定理得：所以：于是得：這與G是簡單平面圖矛盾。例3求證：若G是連通平面圖，且所有頂點(diǎn)度數(shù)不小于3，則G至少有一個面f，使得：deg(f)≦5。23例2求證，沒有6連通簡單可平面圖。證明證明：若不然，則：由歐拉公式得：于是得：另一方面：由δ(G)≥3得：2m≥3n>3n-6這樣導(dǎo)出矛盾。例4設(shè)G是一個(n,m)圖。求證：若G是外可平面圖，且沒有三角形，則：m≦(3n-4)/224證明：若不然，則：由歐拉公式得：于是證明：由條件易知：由歐拉公式得：于是得：例5設(shè)G是一個(n,m)單圖，圖G分解為可平面的最少個數(shù)稱為G的厚度θ(G).求證：

(1)25證明：由條件易知：由歐拉公式得：于是

(2)證明:(1)當(dāng)n=1時，結(jié)論成立。設(shè)當(dāng)n≥3時，G分解為θ(G)個可平面子圖Gi(1≦i≦θ(G))因?yàn)槊總€Gi是平面單圖，于是：所以：所以：26(2)證明:(1)當(dāng)n=1時，結(jié)論成立

(2)因?yàn)镵3,K4是平面圖，所以θ(K3)=θ(K4)=1，而直接計(jì)算：當(dāng)5≦n≦8時，Kn是非完全圖。因?yàn)榇嬖?階簡單可平面圖G，其補(bǔ)圖也是可平面圖，所以對5≦n≦8，Kn可以分解為兩個可平面圖，即：θ(Kn)=2(5≦n≦8).另一方面：當(dāng)5≦n≦8時，直接計(jì)算知：這就證明了(2)。27(2)因?yàn)镵3,K4是平面圖，所以θ(K3)=說明：習(xí)題6的1----9題比較簡單，要求自己獨(dú)立完成。沒有講到的習(xí)題，作為參考。28說明：習(xí)題6的1----9題比較簡單，要求自己獨(dú)立完

作業(yè)

P143---146習(xí)題6：1----929作業(yè)P143---146習(xí)題6：1----9ThankYou!30ThankYou!30

圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院31圖論及其應(yīng)用應(yīng)用數(shù)學(xué)學(xué)院1本次課主要內(nèi)容(一)、涉及算法的相關(guān)概念(二)、平面性算法平面性算法32本次課主要內(nèi)容(一)、涉及算法的相關(guān)概念(二)、平面性算法平關(guān)于圖的平面性問題，我們建立了一些可平面性判定方法：(一)、涉及算法的相關(guān)概念

(1)對于簡單圖G=(n,m)，如果m>3n-6，則G是非可平面的；

(2)對于連通圖G=(n,m)，如果每個面次數(shù)至少為l≥3,且m>(n-2)l/(l-2)，則G是非可平面的；

(3)庫拉托斯基定理：G是可平面的當(dāng)且僅當(dāng)G不含有與K5或K3,3同胚的子圖；

(4)瓦格納定理：G是可平面的當(dāng)且僅當(dāng)G不含有能夠收縮成K5或K3,3的子圖；33關(guān)于圖的平面性問題，我們建立了一些可平面性判定方法上面的方法，局限性很大。這次課我們將給出一個算法，其作用是：如果G非可平面，通過算法可以得到判定；如果G是可平面圖，通過算法，可以給出一種平面嵌入形式。定義1設(shè)H是G的一個子圖，在E(G)-E(H)中定義一個二元關(guān)系“~”:

(1)e1與e2分別是W的始邊和終邊，且

(2)W與H的內(nèi)點(diǎn)不能相交。容易驗(yàn)證：上面的關(guān)系是E(G)-E(H)元間的等價(jià)關(guān)系。34上面的方法，局限性很大。這次課我們將給出一個算法，定義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的所有橋。GGB1B2B3B435定義2設(shè)B是E(G)-E(H)關(guān)于二元關(guān)系“~定義3設(shè)H是圖G的可平面子圖，是H的一種平面嵌入。若G也是可平面圖，且存在G的一個平面嵌入，且：稱是G容許的。例2在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取容易知道：是G容許的。G36定義3設(shè)H是圖G的可平面子圖，是H的一例3在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取容易知道：不是G容許的。定義4設(shè)B是G中子圖H的任意一座橋，若B對H的所有附著頂點(diǎn)都位于的某個面f的邊界上，則稱B在面f內(nèi)可畫入，否則，稱B在面f內(nèi)不可畫入。37例3在G中，我們?nèi)〖t色邊導(dǎo)出的子圖為H,并取對于G的橋B,令：例4紅色邊的導(dǎo)出子圖是H,如果取確定H的橋在中可以畫入的面集合。B3B2B1f3f2f1G解：38對于G的橋B,令：例4紅色邊的導(dǎo)出子圖是H定理1設(shè)是G容許的，則對于H的每座橋B:證明：因是G容許的，由定義，存在G的一個平面嵌入，使得：于是，H的橋B所對應(yīng)的的子圖，必然限制在的某個面內(nèi)。所以：注：定理1實(shí)際上給出了一個圖是可平面圖的一個必要條件。這個必要條件表明：如果存在G的一個可平面子圖H,39定理1設(shè)是G容許的，則對于H的每使得對于某橋B，有，那么，G是非可平面的。根據(jù)上面的結(jié)論：我們可以按如下方式來考慮G的平面性問題：先取G的一個可平面子圖H1,其平面嵌入是對于H1的每座橋B,如果：，則G非可平面。否則，取H1的橋B1,作：H2=B1∪H1,再取一個面將B1畫入的面f中。40使得對于某橋B，有如果B1可平面，則只要把B1平面嵌入后，得到H2的平面嵌入然后再進(jìn)行上面相同的操作，可以得到G的邊數(shù)遞增的子圖平面嵌入序列：最終，得到可平面圖G的一種平面嵌入形式。(二)、平面性算法

1964年，Demoucron,Mlgrance和Pertuiset提出了下面的平面性算法，簡稱DMP算法。41如果B1可平面，則只要把B1平面嵌入后，得到H2的平設(shè)G是至少三個頂點(diǎn)的簡單塊。

(1)取G的一個圈H1,求出H1的一個平面嵌入。置i=1;

(2)若E(G)-E(Hi)=Φ,則停止；否則，確定G中Hi的所有橋，并對每座橋B，求出；

(3)若存在橋B,使得：，則停止(G不可平面)；否則，在Hi的所有橋中確定一個使得最小的B，并取。

(4)在橋B中取一條連接Hi中兩個附著頂點(diǎn)的路Pi,置Hi+1=Hi∪Pi,把Pi畫在的面f內(nèi),得到42設(shè)G是至少三個頂點(diǎn)的簡單塊。(1)取G的一

(5)置i=i+1轉(zhuǎn)(2)。例5用平面性算法考察下圖G的平面性。v6v5v4v3v2v1v8v7圖G解：(1)取G的一個圈H1,并作平面嵌入：43(5)置i=i+1轉(zhuǎn)(2)。例5用平面性v6v5v4v3v2v1v8v7圖G

(2)v6v5v4v3v2v1v8v7H1v6v5v4v3v2v1v8v7f1f244v6v5v4v3v2v1v8v7圖G(2)v6v5vv6v5v4v3v2v1v8v7圖G

(3)取B1和f1.(4)取P1=v1v3f3v6v5v4v3v2v1v8v7f1f245v6v5v4v3v2v1v8v7圖G(3)取B1和v6v5v4v3v2v1v8v7圖G

(3)取B2和f3.(4)取P2=v2v7v6v5v4v3v2v1v8v7f1f2f346v6v5v4v3v2v1v8v7圖G(3)取B2和v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1v8v7f1f2f3f447v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1

(3)取B1和f1.(4)取P3=v1v4v6v5v4v3v2v1v8v7圖Gv6v5v4v3v2v1v8v7f1f2f3f5f448(3)取B1和f1.(4)取P3=v1vv6v5v4v3v2v1v8v7圖G

(3)取B1和f5.(4)取P4=v2v6v6v5v4v3v2v1v8v7f1f2f3f6f4f549v6v5v4v3v2v1v8v7圖G(3)取B1和v6v5v4v3v2v1v8v7圖G繼續(xù)下去，得到：v6v5v4v3v2v1v8v7算法分析：主要運(yùn)算包括：50v6v5v4v3v2v1v8v7圖G繼續(xù)下去，得到：（i）找出塊G中的一個圈Hi；（ii）確定G中Hi的橋以及它們對于Hi的附著點(diǎn)；（iii）對于的每個面f確定其周界；（iv）對于的每座橋B，確定（v）在Hi的某座橋B中求一條起點(diǎn)與終點(diǎn)均為附著點(diǎn)的一條路Pi。

可證上述每一個算法均存在好算法，因此平面性算法也是好算法。本章部分習(xí)題解答51（i）找出塊G中的一個圈Hi；（ii）確定G中Hi的橋以及它例1求證，每個5連通簡單可平面圖至少有12個頂點(diǎn)。證明：設(shè)G是5連通圖，則：由惠特尼定理得：所以：另一方面：G是5連通簡單可平面圖，所以有：于是得：即：所以：n≥12。52例1求證，每個5連通簡單可平面圖至少有12個頂點(diǎn)。例2求證，沒有6連通簡單可平面圖。證明：若不然，設(shè)