特殊平面圖與平面圖的對偶圖實(shí)用教案

1、1 1、極大(j d)平面圖及其性質(zhì)(一)、一些(yxi)特殊平面圖 對于一個(gè)簡單平面圖來說，在不鄰接頂點(diǎn)對間加邊，當(dāng)邊數(shù)增加到一定數(shù)量時(shí)，就會(huì)變成非平面圖。這樣(zhyng)，就啟發(fā)我們研究平面圖的極圖問題。 定義1 設(shè)G是簡單可平面圖，如果G是Ki (1i4),或者在G的任意非鄰接頂點(diǎn)間添加一條邊后，得到的圖均是非可平面圖，則稱G是極大可平面圖。 極大可平面圖的平面嵌入稱為極大平面圖。第1頁/共32頁第一頁，共32頁。2 注：只有(zhyu)在單圖前提下才能定義極大平面圖。 引理 設(shè)G是極大平面圖，則G必然(brn)連通；若G的階數(shù)大于等于3，則G無割邊。極大平面圖非極大平面圖極大平面圖

2、(1) 先證明(zhngmng)G連通。 若不然，G至少兩個(gè)連通分支。設(shè)G1與G2是G的任意兩個(gè)連通分支。第2頁/共32頁第二頁，共32頁。3 把G1畫在G2的外部面上，并在G1,G2上分別取一點(diǎn)(y din)u與v.連接u與v得到一個(gè)新平面圖G*。但這與G是極大平面圖相矛盾。 (2) 當(dāng)G的階數(shù)n3時(shí)，我們(w men)證明G中沒有割邊。 若不然，設(shè)G中有割邊e = uv，則G-uv不連通(lintng)，恰有兩個(gè)連通(lintng)分支G1與G2。uveG1G2Gf第3頁/共32頁第三頁，共32頁。4 設(shè)u在G1中，而v在G2中。由于n3, 所以，至少有一個(gè)分支包含兩個(gè)以上的頂點(diǎn)(dngd

3、in)。設(shè)G2至少含有兩個(gè)頂點(diǎn)(dngdin)。又設(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多一條(y tio)邊。這與G的極大性相矛盾。vueG1G2G第4頁/共32頁第四頁，共32頁。5 下面(xi mian)證明極大平面圖的一個(gè)重要性質(zhì)。 定理1 設(shè)G是至少有3個(gè)頂點(diǎn)(dngdin)的平面圖，則G是極大平面圖，當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)是3且為單圖。 注：該定理可以(ky)簡單記為是“極大平面圖的三角形特征”，即每個(gè)面的邊界是三角形。 證明：“必要性” 由引理知，G是單圖、G

4、無割邊。于是G的每個(gè)面的次數(shù)至少是3。 假設(shè)G中某個(gè)面 f 的次數(shù)大于等于4。記 f 的邊界是v1v2v3v4vk。如下圖所示:第5頁/共32頁第五頁，共32頁。6 如果v1與v3不鄰接，則連接v1v3，沒有破壞G的平面性，這與G是極大平面圖矛盾。所以v1v3必須(bx)鄰接，但必須(bx)在 f 外連線；同理v2與v4也必須(bx)在 f 外連線。但邊v1v3與邊v2v4在 f 外交叉，與G是平面圖矛盾！ 所以(suy)，G的每個(gè)面次數(shù)一定是3. 定理(dngl)的充分性是顯然的。v1v2v3v4v5vkf第6頁/共32頁第六頁，共32頁。7 推論(tuln)：設(shè)G是n個(gè)點(diǎn)，m條邊和個(gè)面的極

5、大平面圖，且n3.則：(1) m=3n-6; (2) =2n-4. 證明：因?yàn)镚是極大平面圖，所以，每個(gè)面的次數(shù)(csh)為3.由次數(shù)(csh)公式：2deg()3fmf 由歐拉公式(gngsh)：2nm 所以得：223mnm第7頁/共32頁第七頁，共32頁。8 所以(suy)得：36mn 又2mn 所以(suy)：24n 注：頂點(diǎn)數(shù)相同(xin tn)的極大平面圖并不唯一。例如：正20面體非正20面體第8頁/共32頁第八頁，共32頁。9 還在研究中的問題是：頂點(diǎn)數(shù)相同的極大(j d)平面圖的個(gè)數(shù)和結(jié)構(gòu)問題。 2、極大(j d)外平面圖及其性質(zhì) 定義2 若一個(gè)(y )可平面圖G存在一種平面嵌入

6、，使得其所有頂點(diǎn)均在某個(gè)面的邊界上，稱該圖為外可平面圖。外可平面圖的一種外平面嵌入，稱為外平面圖。外可平面圖外平面圖1f外平面圖2f第9頁/共32頁第九頁，共32頁。10 注：對外可平面圖G來說，一定存在一種外平面嵌入，使得G的頂點(diǎn)(dngdin)均在外部面的邊界上。這由球極投影法可以說明。 下面(xi mian)研究極大外平面圖的性質(zhì)。 定義3 設(shè)G是一個(gè)簡單外可平面圖，若在G中任意(rny)不鄰接頂點(diǎn)間添上一條邊后，G成為非外可平面圖，則稱G是極大外可平面圖。極大外可平面圖的外平面嵌入，稱為極大外平面圖。極大外平面圖第10頁/共32頁第十頁，共32頁。11 定理2 設(shè)G是一個(gè)有n (n3)

7、個(gè)點(diǎn)，且所有點(diǎn)均在外部面上(min shn)的極大外平面圖，則G有n-2個(gè)內(nèi)部面。 證明：對G的階數(shù)作數(shù)學(xué)(shxu)歸納。 當(dāng)n=3時(shí)，G是三角形，顯然只有(zhyu)一個(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è)連通簡單外可平面圖，則在G中有一個(gè)度數(shù)至多是2的頂點(diǎn)。第11頁/共32頁第十一頁，共32頁。12 定理3 設(shè)G是一個(gè)有n (n3)個(gè)點(diǎn)，且所有點(diǎn)均在外部(wib)面上的外平面圖，則G是極大外

8、平面圖，當(dāng)且僅當(dāng)其外部(wib)面的邊界是圈，內(nèi)部面是三角形。 注：這是極大外平面圖的典型(dinxng)特征。 證明(zhngmng)：先證明(zhngmng)必要性。 (1) 證明G的邊界是圈。 容易知道：G的外部面邊界一定為閉跡，否則，G不能為極大外平面圖。設(shè)W=v1v2vnv1是G的外部面邊界。若W不是圈，則存在i與j, 使vi=vj=v.此時(shí)，G可以示意如下：W vi-1 v1vnv2vi+1vj-1vj+1v第12頁/共32頁第十二頁，共32頁。13 vi-1與vi+1不能鄰接。否則W不能構(gòu)成G的外部面邊界。這樣(zhyng)，我們連接vi-1與vi+1： vi-1 v1vnv2v

9、i+1vj-1vj+1v 得到一個(gè)新外平面圖。這與G的極大(j d)性矛盾。 (2) 證明(zhngmng)G的內(nèi)部面是三角形。 首先，注意到，G的內(nèi)部面必須是圈。因?yàn)?，G的外部面的邊界是生成圈，所以G是2連通的，所以，G的每個(gè)面的邊界必是圈。第13頁/共32頁第十三頁，共32頁。14 其次，設(shè)C是G中任意一個(gè)內(nèi)部面的邊界。如果(rgu)C的長度大于等于4，則C中一定存在不鄰接頂點(diǎn)，連接這兩點(diǎn)得到一個(gè)新平面圖，這與G的極大性矛盾。又由于G是單圖，所以C的長度只能為3. 下面(xi mian)證明充分性。 設(shè)G是一個(gè)(y )外平面圖，內(nèi)部面是三角形，外部面是圈W. 如果G不是極大外平面圖，那么存

10、在不鄰接頂點(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是極大外平面圖。第14頁/共32頁第十四頁，共32頁。15 定理4 每個(gè)至少有7個(gè)頂點(diǎn)的外可平面圖的補(bǔ)圖不是(b shi)外可平面圖，且7是這個(gè)數(shù)目的最小者。 我們(w men)用枚舉方法證明。 證明：對于n=7的極大(j d)外可平面圖來說，只有4個(gè)。如下圖所示。 直接驗(yàn)證：它們的補(bǔ)圖均不是外可平面的。 而當(dāng)n=6時(shí)，我們可以找到一個(gè)外可平面圖G(見下圖),使得其補(bǔ)圖是外可平面圖。第15頁/共32頁第十五

11、頁，共32頁。16GG(二)、平面圖的對偶(du u)圖 1、對偶(du u)圖的定義 定義4 給定(i dn)平面圖G，G的對偶圖G*如下構(gòu)造： (1) 在G的每個(gè)面fi內(nèi)取一個(gè)點(diǎn)vi*作為G*的一個(gè)頂點(diǎn)； (2) 對G的一條邊e, 若e是面 fi 與 fj 的公共邊，則連接vi*與vj*，且連線穿過邊e;若e是面 fi 中的割邊，則以vi為頂點(diǎn)第16頁/共32頁第十六頁，共32頁。17作環(huán)，且讓它與e相交(xingjio)。 例如(lr)，作出平面圖G的對偶圖G*G第17頁/共32頁第十七頁，共32頁。18 2、對偶(du u)圖的性質(zhì) (1)、G與G*的對應(yīng)(duyng)關(guān)系 1) G*

12、的頂點(diǎn)(dngdin)數(shù)等于G的面數(shù)； 2) G*的邊數(shù)等于G的邊數(shù)； 3) G*的面數(shù)等于G的頂點(diǎn)數(shù)； 4) d (v*)=deg( f )對偶圖面邊割邊環(huán)邊割集回路點(diǎn)邊環(huán)割邊回路邊割集對 應(yīng)平面圖G第18頁/共32頁第十八頁，共32頁。19 (2)、定理(dngl)5 定理5 平面圖G的對偶(du u)圖必然連通 證明(zhngmng)：在G*中任意取兩點(diǎn)vi*與vj*。我們證明(zhngmng)該兩點(diǎn)連通即可！ 用一條曲線 l 把vi*和vj*連接起來，且 l 不與G*的任意頂點(diǎn)相交。 顯然，曲線 l 從vi*到vj*經(jīng)過的面邊序列，對應(yīng)從vi*到vj*的點(diǎn)邊序列，該點(diǎn)邊序列就是該兩點(diǎn)在

13、G*中的通路。 注: (1) 由定理5知：(G*)*不一定等于G;第19頁/共32頁第十九頁，共32頁。20 證明(zhngmng)：“必要性” (2) G是平面圖，則 當(dāng)且僅當(dāng)G是連通(lintng)的。(習(xí)題第26題)( *)*GG 由于G是平面圖，由定理(dngl)5，G*是連通的。而由G*是平面圖，再由定理(dngl)5，(G*)*是連通的。 所以，由 得：G是連通的。( *)*GG “充分性” 由對偶圖的定義知，平面圖G與其對偶圖G*嵌入在同一平面上，當(dāng)G連通時(shí)，容易知道：G*的無界面 f *中僅含G的唯一頂點(diǎn)v,而除v外，G中其它頂點(diǎn)u均與G*的有限面形成一一對應(yīng)，于是，G中頂點(diǎn)和

14、G*頂點(diǎn)在這種自然對應(yīng)方式下一一對應(yīng)，且對應(yīng)頂點(diǎn)間鄰接關(guān)系保持不變，故：( *)*GG第20頁/共32頁第二十頁，共32頁。21 (3) 同構(gòu)的平面圖可以(ky)有不同構(gòu)的對偶圖。 例如(lr)，下面的兩個(gè)圖：12GGG1G2 但12*GG 這是因?yàn)椋篏2中有次數(shù)是1的面，而G1沒有次數(shù)是1的面。所以，它們(t men)的對偶圖不能同構(gòu)。第21頁/共32頁第二十一頁，共32頁。22 第一次上交(shn jio)作業(yè) 第3章 習(xí)題(xt)3 ：1，7，9，16. 第4章 習(xí)題(xt)4 ：3，7，10，12. 第5章 習(xí)題5 ：1，2，6，7，13，19。第22頁/共32頁第二十二頁，共32頁。

15、23 作業(yè)(zuy) P143-146 習(xí)題(xt)5 ：3，4，5，6，8， 25, 26，27。 其中 25，26，27結(jié)合(jih)課件學(xué)習(xí)。第23頁/共32頁第二十三頁，共32頁。24Thank You !第24頁/共32頁第二十四頁，共32頁。25 例2 證明(zhngmng)：*( *)*cE GcBC (1) B是平面圖G的極小(j xio)邊割集，當(dāng)且僅當(dāng) 是G*的圈。 (2) 歐拉平面圖的對偶(du u)圖是偶圖。示意圖第25頁/共32頁第二十五頁，共32頁。26 證明(zhngmng): (1) 對B的邊數(shù)作數(shù)學(xué)(shxu)歸納。示意圖 當(dāng)B的邊數(shù)n=1時(shí)，B中邊是割邊 顯

16、然，在G*中對應(yīng)環(huán)。所以，結(jié)論(jiln)成立。 設(shè)對B的邊數(shù)nk 時(shí)，結(jié)論成立?？紤]n=k的情形。 設(shè)c1 B, 于是B-c1是G-c1=G1的一個(gè)極小邊割集。由歸納假設(shè)：111*(*)*cE GcBcC 是G1*的一個(gè)圈。且圈C1*上的頂點(diǎn)對應(yīng)于G1中的面f, f 的邊界上有極小邊割集B-e1的邊。第26頁/共32頁第二十六頁，共32頁。27 現(xiàn)在(xinzi)，把e1加入到G1中，恢復(fù)G。示意圖G1 由于(yuy)G是平面圖，其作用相當(dāng)于圈C1*上的一個(gè)頂點(diǎn)對應(yīng)于G1中的一個(gè)平面區(qū)域 f, 被e1劃分成兩個(gè)頂點(diǎn)f1*與f2*,并在其間連以e1所對應(yīng)的邊e1*。 所以，B對應(yīng)在G*中的C*

17、仍然是一個(gè)圈。由歸納法，結(jié)論得到(d do)證明。示意圖第27頁/共32頁第二十七頁，共32頁。28 充分性： G*中的一個(gè)圈，對應(yīng)(duyng)于G中 的邊的集合B顯然(xinrn)是G中的一個(gè)邊割集。 示意圖 若該割集不是極小邊割集，則它是G中極小邊割集之和。而由必要性知道：每個(gè)極小邊割集對應(yīng)G*的一個(gè)圈，于是推出B在G*中對應(yīng)的邊集合(jh)是圈之并。但這與假設(shè)矛盾。 (2) 因歐拉圖的任意邊割集均有偶數(shù)條邊。于是由(1),G*中不含奇圈。所以G*是偶圖。第28頁/共32頁第二十八頁，共32頁。29 例3 設(shè)T是連通(lintng)平面圖G的生成樹，*( *)( )EeE GeE T 證明：T*=G*E*是G*中的生成(shn chn)樹。(習(xí)題第27題)示意圖第29頁/共32頁第二十九頁，共32頁。30 證明(zhngmng)：情形1，如果G是樹。 在這種情況下，E* = .則T*是平凡圖，而G*的生成(shn chn)樹也是平凡圖，所以，結(jié)論成立； 情形2，如果(rgu)G不是樹。 因G的每個(gè)面必然含有邊e不屬于E(T),即G*的每個(gè)頂點(diǎn)必然和E*中的某邊關(guān)聯(lián)，于是T*必然是G*的生成子圖。 下面證明