圖論課件第六章 平面圖.ppt

1、1,圖論及其應用,應用數學學院,2,第六章 平面圖,主要內容,一、平面圖概念與性質,二、特殊平面圖與平面圖的對偶圖,三、平面圖的判定與涉及平面性不變量,教學時數,安排8學時講授本章內容,四、平面性算法,3,本次課主要內容,(一)、平面圖的概念,(二)、平面圖性質,平面圖概念與性質,(三)、圖的嵌入性問題簡介,(四)、凸多面體與平面圖,4,圖的平面性問題是圖論典型問題之一。生活中許多問題都與該問題有關。,(一)、平面圖的概念,例子1：電路板設計問題,在電路板設計時，需要考慮的問題之一是連接電路元件間的導線間不能交叉。否則，當絕緣層破損時，會出現短路故障。,顯然，電路板可以模型為一個圖，“要求電路

2、元件間連接導線互不交叉”，對應于“要求圖中的邊不能相互交叉”。,5,例子2：空調管道的設計,某娛樂中心有6個景點，位置分布如下圖。,分析者認為：(1) A1與A4, (2) A2與A5, (3) A3與A6間人流較少，其它景點之間人流量大，必須投資鋪設空調管道，但要求空調管道間不能交叉。如何設計？,6,如果把每個景點分別模型為一個點，景點間連線，當且僅當兩景點間要鋪設空調管道。那么，上面問題直接對應的圖為：,于是，問題轉化為：能否把上圖畫在平面上，使得邊不會相互交叉？,7,通過嘗試，可以把上圖畫為：,于是，鋪設方案為：,8,問題：要求把3種公用設施(煤氣，水和電)分別用煤氣管道、水管和電線連接

3、到3間房子里，要求任何一根線或管道不與另外的線或管道相交，能否辦到？,例子3：3間房子和3種設施問題,上面問題可以模型為如下偶圖：,問題轉化為，能否把上面偶圖畫在平面上，使得邊與邊之間不會交叉？,9,上面的例子都涉及同一個圖論問題：能否把一個圖畫在平面上，使得邊與邊之間沒有交叉？,針對這一問題，我們引入如下概念,定義1 如果能把圖G畫在平面上，使得除頂點外，邊與邊之間沒有交叉，稱G可以嵌入平面，或稱G是可平面圖?？善矫鎴DG的邊不交叉的一種畫法，稱為G的一種平面嵌入，G的平面嵌入表示的圖稱為平面圖。,10,注: (1) 可平面圖概念和平面圖概念有時可以等同看待；,(2) 圖的平面性問題主要涉及如

4、下幾個方面：1) 平面圖的性質；2) 平面圖的判定；3) 平面嵌入方法(平面性算法) ;4）涉及圖的平面性問題的拓撲不變量。,由 圖的平面性問題研究引申出圖的一般嵌入性問題的研究，形成了拓撲圖論的主要內容。我國數學家吳文俊、劉彥佩等在該方向都有重要結果。劉彥佩的專著是圖的上可嵌入性理論(1994)，化學工業(yè)出版社出版。,歷史上，波蘭數學家?guī)炖兴够?、美國數學家惠特尼、生于英國的加拿大數學家托特，我國數學家吳文俊等都在拓撲圖論中有過精湛的研究。,11,(二)、平面圖性質,定義2 (1) 一個平面圖G把平面分成若干連通片，這些連通片稱為G的區(qū)域，或G的一個面。G的面組成的集合用表示。,在上圖G中，

5、共有4個面。其中f4是外部面，其余是內部面。=f1, f2, f3, f4。,(2) 面積有限的區(qū)域稱為平面圖G的內部面，否則稱為G的外部面。,12,(3) 在G中，頂點和邊都與某個給定區(qū)域關聯的子圖，稱為該面的邊界。某面 f 的邊界中含有的邊數(割邊計算2次)稱為該面 f 的次數, 記為deg ( f )。,在上圖中，紅色邊在G中的導出子圖為面 f3 的邊界。,1、平面圖的次數公式,13,定理1 設G=(n, m)是平面圖，則：,證明：對G的任意一條邊e, 如果e是某面割邊，那么由面的次數定義，該邊給G的總次數貢獻2次；如果e不是割邊，那么，它必然是兩個面的公共邊，因此，由面的次數定義，它也

6、給總次數貢獻2次。于是有：,2、平面圖的歐拉公式,14,定理2(歐拉公式) 設G=(n, m)是連通平面圖，是G的面數，則：,證明：情形1，如果G是樹，那么m=n-1, =1。在這種情況下，容易驗證，定理中的恒等式是成立的。,情形2，G不是樹的連通平面圖。,假設在這種情形下，歐拉恒等式不成立。則存在一個含有最少邊數的連通平面圖G, 使得它不滿足歐拉恒等式。設這個最少邊數連通平面圖G=(n, m), 面數為，則：,15,因為G不是樹，所以存在非割邊e。顯然，G-e是連通平面圖，邊數為m-1, 頂點數為n, 面數為-1。,由最少性假設，G-e滿足歐拉等式：,化簡得：,這是一個矛盾。,注：該定理可以

7、采用對面數作數學歸納證明。,3、歐拉公式的幾個有趣推論,16,推論1 設G是具有個面k個連通分支的平面圖，則：,證明：對第i (1ik)個分支來說，設頂點數為ni，邊數為mi，面數為i,由歐拉公式：,所以，,17,而：,所以得：,推論2 設G是具有n個點m條邊個面的連通平面圖，如果對G的每個面f ,有：deg (f) l 3,則：,18,證明：一方面，由次數公式得：,另一方面，由歐拉公式得：,所以有：,整理得：,19,注: (1)上面推論2也可以敘述為：,設G=(n, m)是連通圖，如果：,則G是非可平面圖。,(2) 推論2的條件是G是平面圖的必要條件,不是充分條件。,例1 求證：K3,3是非

8、可平面圖。,證明：注意到，K3,3是偶圖，不存在奇圈，所以，每個面的次數至少是4,即 l=4,20,所以，,而m=9，這樣有：,所以，由推論2，K3,3是非平面圖。,推論3 設G是具有n個點m條邊個面的簡單平面圖，則：,21,證明：情形1，G連通。,因為G是簡單圖，所以每個面的次數至少為3，即l=3。于是，由推論2得：,情形2，若G不連通。設G1,G2,Gk是連通分支。,一方面,由推論1：,另一方面，由次數公式得：,所以得：,22,例2，證明：K5是非可平面圖。,證明：K5是簡單圖，m=10, n=5。3n-6=9。,得， ，所以K5是非可平面圖。,推論4 設G是具有n個點m條邊的連通平面圖，

9、若G的每個圈均由長度是 l 的圈圍成，則：,證明：由次數公式，歐拉公式容易得證。,23,推論5 設G是具有n個點m條邊的簡單平面圖，則：,證明：若不然，設,由握手定理：,這與G是簡單平面圖矛盾。,注：該結論是證明“5色定理”的出發(fā)點。,24,定理3 一個連通平面圖是2連通的，當且僅當它的每個面的邊界是圈。,證明：“必要性”： 設G是2連通的平面圖，因為環(huán)總是兩個面的邊界，且環(huán)面顯然由圈圍成。不失一般性，假設G沒有環(huán)，那么G沒有割邊，也沒有割點。所以，每個面的邊界一定是一條閉跡。,設C是G的任意面的一個邊界，我們證明，它一定為圈。,若不然，設C是G的某面的邊界，但它不是圈。,因C是一條閉跡且不是

10、圈，因此，C中存在子圈。設該子圈是W1.因C是某面的邊界，所以W1與C的關系可以表示為下圖的形式：,25,容易知道：v為G的割點。矛盾！,“充分性” 設平面圖G的每個面的邊界均為圈。此時刪去G中任意一個點不破壞G的連通性，這表明G是2連通的。,推論6 若一個平面圖是2連通的，則它的每條邊恰在兩個面的邊界上。,26,(三)、圖的嵌入性問題簡介,在圖的平面嵌入的基礎上，簡單介紹：,1、曲面嵌入,1)、球面嵌入,定理4 G可球面嵌入當且僅當G可平面嵌入。,證明：我們用建立球極平面射影的方法給出證明。,將求面S放在一個平面P上，設切點為O，過O作垂直于P的直線，該直線與S相交于z。,27,2)、環(huán)面嵌

11、入,環(huán)面的形狀像一個汽車輪胎的表面。,作映射 f : S -z P。定義 f (x) = y, 使得x ,y , z三點共線。該映射稱為球極平面射影。,通過f, 可以把嵌入球面的圖映射為嵌入平面的圖。反之亦然。,28,例3 將K4, K5, K3,3嵌入到環(huán)面上。,3) 定向曲面嵌入,這是目前嵌入性問題研究熱點。國內：劉彥佩，黃元秋等是從事該方向研究的代表。,29,2、圖的3維空間嵌入,定理5 所有圖均可嵌入R3中。,證明：在R3中作空間曲線：,把圖G的頂點放在該直線的不同位置，則G的任意邊不相交。,事實上，對處于曲線 l 上的任意4個相異頂點，它們對應的參數值分別為：t1,t2,t3,t4。,30,因為：,所以，上面4點不共面。,(四)、凸多面體與平面圖,一個多面體稱為凸多面體，如果在體上任取兩點，其連線均在體上。,凸多面體的一維骨架：把一個凸多面體壓縮在平面上，得到一個對應的平面圖，該平面圖稱為該凸多面體的一維骨架。,31,定理6 存在且只存在5種正多面體：它們是正四、六、八、十二、二十面體。,證明：任取一個正面體，其頂點數、棱數分別是n和m。對