ppt20電子科大圖論上課ppt及復(fù)習(xí)總結(jié)楊春.ppt

1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,第六章 平面圖,主要內(nèi)容,一、平面圖概念與性質(zhì),二、特殊平面圖與平面圖的對(duì)偶圖,三、平面圖的判定與涉及平面性不變量,教學(xué)時(shí)數(shù),安排8學(xué)時(shí)講授本章內(nèi)容,四、平面性算法,3,本次課主要內(nèi)容,(一)、平面圖的概念,(二)、平面圖性質(zhì),平面圖概念與性質(zhì),(三)、圖的嵌入性問題簡(jiǎn)介,(四)、凸多面體與平面圖,4,圖的平面性問題是圖論典型問題之一。生活中許多問題都與該問題有關(guān)。,(一)、平面圖的概念,例子1：電路板設(shè)計(jì)問題,在電路板設(shè)計(jì)時(shí)，需要考慮的問題之一是連接電路元件間的導(dǎo)線間不能交叉。否則，當(dāng)絕緣層破損時(shí)，會(huì)出現(xiàn)短路故障。,顯然，電路板可以模型為一個(gè)圖，“要求電路元件間連接導(dǎo)線互不交叉”，對(duì)應(yīng)于“要求圖中的邊不能相互交叉”。,5,例子2：空調(diào)管道的設(shè)計(jì),某娛樂中心有6個(gè)景點(diǎn)，位置分布如下圖。,分析者認(rèn)為：(1) A1與A4, (2) A2與A5, (3) A3與A6間人流較少，其它景點(diǎn)之間人流量大，必須投資鋪設(shè)空調(diào)管道，但要求空調(diào)管道間不能交叉。如何設(shè)計(jì)？,6,如果把每個(gè)景點(diǎn)分別模型為一個(gè)點(diǎn)，景點(diǎn)間連線，當(dāng)且僅當(dāng)兩景點(diǎn)間要鋪設(shè)空調(diào)管道。那么，上面問題直接對(duì)應(yīng)的圖為：,于是，問題轉(zhuǎn)化為：能否把上圖畫在平面上，使得邊不會(huì)相互交叉？,7,通過嘗試，可以把上圖畫為：,于是，鋪設(shè)方案為：,8,問題：要求把3種公用設(shè)施(煤氣，水和電)分別用煤氣管道、水管和電線連接到3間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？,例子3：3間房子和3種設(shè)施問題,上面問題可以模型為如下偶圖：,問題轉(zhuǎn)化為，能否把上面偶圖畫在平面上，使得邊與邊之間不會(huì)交叉？,9,上面的例子都涉及同一個(gè)圖論問題：能否把一個(gè)圖畫在平面上，使得邊與邊之間沒有交叉？,針對(duì)這一問題，我們引入如下概念,定義1 如果能把圖G畫在平面上，使得除頂點(diǎn)外，邊與邊之間沒有交叉，稱G可以嵌入平面，或稱G是可平面圖?？善矫鎴DG的邊不交叉的一種畫法，稱為G的一種平面嵌入，G的平面嵌入表示的圖稱為平面圖。,10,注: (1) 可平面圖概念和平面圖概念有時(shí)可以等同看待；,(2) 圖的平面性問題主要涉及如下幾個(gè)方面：1) 平面圖的性質(zhì)；2) 平面圖的判定；3) 平面嵌入方法(平面性算法) ;4）涉及圖的平面性問題的拓?fù)洳蛔兞俊?由 圖的平面性問題研究引申出圖的一般嵌入性問題的研究，形成了拓?fù)鋱D論的主要內(nèi)容。我國(guó)數(shù)學(xué)家吳文俊、劉彥佩等在該方向都有重要結(jié)果。劉彥佩的專著是圖的上可嵌入性理論(1994)，化學(xué)工業(yè)出版社出版。,歷史上，波蘭數(shù)學(xué)家?guī)炖兴够?、美?guó)數(shù)學(xué)家惠特尼、生于英國(guó)的加拿大數(shù)學(xué)家托特，我國(guó)數(shù)學(xué)家吳文俊等都在拓?fù)鋱D論中有過精湛的研究。,11,(二)、平面圖性質(zhì),定義2 (1) 一個(gè)平面圖G把平面分成若干連通片，這些連通片稱為G的區(qū)域，或G的一個(gè)面。G的面組成的集合用表示。,在上圖G中，共有4個(gè)面。其中f4是外部面，其余是內(nèi)部面。=f1, f2, f3, f4。,(2) 面積有限的區(qū)域稱為平面圖G的內(nèi)部面，否則稱為G的外部面。,12,(3) 在G中，頂點(diǎn)和邊都與某個(gè)給定區(qū)域關(guān)聯(lián)的子圖，稱為該面的邊界。某面 f 的邊界中含有的邊數(shù)(割邊計(jì)算2次)稱為該面 f 的次數(shù), 記為deg ( f )。,在上圖中，紅色邊在G中的導(dǎo)出子圖為面 f3 的邊界。,1、平面圖的次數(shù)公式,13,定理1 設(shè)G=(n, m)是平面圖，則：,證明：對(duì)G的任意一條邊e, 如果e是某面割邊，那么由面的次數(shù)定義，該邊給G的總次數(shù)貢獻(xiàn)2次；如果e不是割邊，那么，它必然是兩個(gè)面的公共邊，因此，由面的次數(shù)定義，它也給總次數(shù)貢獻(xiàn)2次。于是有：,2、平面圖的歐拉公式,14,定理2(歐拉公式) 設(shè)G=(n, m)是連通平面圖，是G的面數(shù)，則：,證明：情形1，如果G是樹，那么m=n-1, =1。在這種情況下，容易驗(yàn)證，定理中的恒等式是成立的。,情形2，G不是樹的連通平面圖。,假設(shè)在這種情形下，歐拉恒等式不成立。則存在一個(gè)含有最少邊數(shù)的連通平面圖G, 使得它不滿足歐拉恒等式。設(shè)這個(gè)最少邊數(shù)連通平面圖G=(n, m), 面數(shù)為，則：,15,因?yàn)镚不是樹，所以存在非割邊e。顯然，G-e是連通平面圖，邊數(shù)為m-1, 頂點(diǎn)數(shù)為n, 面數(shù)為-1。,由最少性假設(shè)，G-e滿足歐拉等式：,化簡(jiǎn)得：,這是一個(gè)矛盾。,注：該定理可以采用對(duì)面數(shù)作數(shù)學(xué)歸納證明。,3、歐拉公式的幾個(gè)有趣推論,16,推論1 設(shè)G是具有個(gè)面k個(gè)連通分支的平面圖，則：,證明：對(duì)第i (1ik)個(gè)分支來說，設(shè)頂點(diǎn)數(shù)為ni，邊數(shù)為mi，面數(shù)為i,由歐拉公式：,所以，,17,而：,所以得：,推論2 設(shè)G是具有n個(gè)點(diǎn)m條邊個(gè)面的連通平面圖，如果對(duì)G的每個(gè)面f ,有：deg (f) l 3,則：,18,證明：一方面，由次數(shù)公式得：,另一方面，由歐拉公式得：,所以有：,整理得：,19,注: (1)上面推論2也可以敘述為：,設(shè)G=(n, m)是連通圖，如果：,則G是非可平面圖。,(2) 推論2的條件是G是平面圖的必要條件,不是充分條件。,例1 求證：K3,3是非可平面圖。,證明：注意到，K3,3是偶圖，不存在奇圈，所以，每個(gè)面的次數(shù)至少是4,即 l=4,20,所以，,而m=9，這樣有：,所以，由推論2，K3,3是非平面圖。,推論3 設(shè)G是具有n個(gè)點(diǎn)m條邊個(gè)面的簡(jiǎn)單平面圖，則：,21,證明：情形1，G連通。,因?yàn)镚是簡(jiǎn)單圖，所以每個(gè)面的次數(shù)至少為3，即l=3。于是，由推論2得：,情形2，若G不連通。設(shè)G1,G2,Gk是連通分支。,一方面,由推論1：,另一方面，由次數(shù)公式得：,所以得：,22,例2，證明：K5是非可平面圖。,證明：K5是簡(jiǎn)單圖，m=10, n=5。3n-6=9。,得， ，所以K5是非可平面圖。,推論4 設(shè)G是具有n個(gè)點(diǎn)m條邊的連通平面圖，若G的每個(gè)圈均由長(zhǎng)度是 l 的圈圍成，則：,證明：由次數(shù)公式，歐拉公式容易得證。,23,推論5 設(shè)G是具有n個(gè)點(diǎn)m條邊的簡(jiǎn)單平面圖，則：,證明：若不然，設(shè),由握手定理：,這與G是簡(jiǎn)單平面圖矛盾。,注：該結(jié)論是證明“5色定理”的出發(fā)點(diǎn)。,24,定理3 一個(gè)連通平面圖是2連通的，當(dāng)且僅當(dāng)它的每個(gè)面的邊界是圈。,證明：“必要性”： 設(shè)G是2連通的平面圖，因?yàn)榄h(huán)總是兩個(gè)面的邊界，且環(huán)面顯然由圈圍成。不失一般性，假設(shè)G沒有環(huán)，那么G沒有割邊，也沒有割點(diǎn)。所以，每個(gè)面的邊界一定是一條閉跡。,設(shè)C是G的任意面的一個(gè)邊界，我們證明，它一定為圈。,若不然，設(shè)C是G的某面的邊界，但它不是圈。,因C是一條閉跡且不是圈，因此，C中存在子圈。設(shè)該子圈是W1.因C是某面的邊界，所以W1與C的關(guān)系可以表示為下圖的形式：,25,容易知道：v為G的割點(diǎn)。矛盾！,“充分性” 設(shè)平面圖G的每個(gè)面的邊界均為圈。此時(shí)刪去G中任意一個(gè)點(diǎn)不破壞G的連通性，這表明G是2連通的。,推論6 若一個(gè)平面圖是2連通的，則它的每條邊恰在兩個(gè)面的邊界上。,26,(三)、圖的嵌入性問題簡(jiǎn)介,在圖的平面嵌入的基礎(chǔ)上，簡(jiǎn)單介紹：,1、曲面嵌入,1)、球面嵌入,定理4 G可球面嵌入當(dāng)且僅當(dāng)G可平面嵌入。,證明：我們用建立球極平面射影的方法給出證明。,將求面S放在一個(gè)平面P上，設(shè)切點(diǎn)為O，過O作垂直于P的直線，該直線與S相交于z。,27,2)、環(huán)面嵌入,環(huán)面的形狀像一個(gè)汽車輪胎的表面。,作映射 f : S -z P。定義 f (x) = y, 使得x ,y , z三點(diǎn)共線。該映射稱為球極平面射影。,通過f, 可以把嵌入球面的圖映射為嵌入平面的圖。反之亦然。,28,例3 將K4, K5, K3,3嵌入到環(huán)面上。,3) 定向曲面嵌入,這是目前嵌入性問題研究熱點(diǎn)。國(guó)內(nèi)：劉彥佩，黃元秋等是從事該方向研究的代表。,29,2、圖的3維空間嵌入,定理5 所有圖均可嵌入R3中。,證明：在R3中作空間曲線：,把圖G的頂點(diǎn)放在該直線的不同位置，則G的任意邊不相交。,事實(shí)上，對(duì)處于曲線 l 上的任意4個(gè)相異頂點(diǎn)，它們對(duì)應(yīng)的參數(shù)值分別為：t1,t2,t3,t4。,30,因?yàn)椋?所以，上面4點(diǎn)不共面。,(四)、凸多面體與平面圖,一個(gè)多面體稱為凸多面體，如果在體上任取兩點(diǎn)，其連線均在體上。,凸多面體的一維骨架：把一個(gè)凸多面體壓縮在平面上，得到一個(gè)對(duì)應(yīng)的平面圖，該平面圖稱為該凸多面體的一維骨架。,31,定理6 存在且只存在5種正多面體：它們是正四、六、八、十二、二十