7-5 平面圖.ppt

1、離散數學Discrete Mathematics,課程回顧,歐拉圖：哥尼斯堡七橋問題、無向歐拉圖定義與判定定理、一筆畫問題、有向歐拉圖定義與判定定理、計算機鼓輪設計及其它應用,漢密爾頓圖：周游世界問題、漢密爾頓圖定義與判定定理、圖的閉包、判別漢密爾頓路不存在的標號法,第七章 圖論第5講 7-5 平面圖7-6 對偶圖與著色,問題引入,例 考慮把三座房和三種 設施每種都連接起來的問題， 如圖7-64所示，是否有可能使 得這樣的連接里不發(fā)生交叉？ 這個問題可以用K3,3來建模。 原來的問題可以重新敘述為： 能否在平面里畫出K3,3 ，使得 沒有兩條邊發(fā)生交叉？,例如印刷線路板上的布線。 在現實生活中

2、，常常要畫一些圖形，希望邊與邊之間盡量減少相交的情況，,7-5 平面圖,學習本節(jié)要熟悉如下術語（8個）：,平面圖、,邊界、,面、,要求： 掌握4個定理，重點掌握歐拉定理。,在2度結點內同構,非平面圖、,有界面、,無界面、,面的次數、,一、平面圖 本節(jié)重點考慮無向圖。 1、定義7-5.1 如果無向圖G=的所有結點和邊可以在一個平面上圖示出來，而使各邊僅在頂點處相交。無向圖G稱為平面圖（planar graph），否則稱G為非平面圖。,有些圖形從表面看有幾條邊是相交的，但是不能就此肯定它不是平面圖。,例1 判斷下面的兩個圖是否為平面圖。,解：K4是平面圖，因為可以不帶交叉地畫出它（圖7-66所示）

3、； Q3是平面圖（圖7-68所示）；,有些圖形不論怎樣改畫，除去結點外，總有邊相交。如K3,3圖，故它是非平面圖。,K3,3,2、面、邊界 定義7-5.2 設G=是一連通平面圖，由圖中的邊所包圍的區(qū)域，在區(qū)域內既不包含圖的結點，也不包含圖的邊，這樣的區(qū)域稱為G的一個面 (regions) ，包圍該面的諸邊所構成的回路稱為這個面的邊界（boundary）。有界的區(qū)域稱為有界面，無界的區(qū)域稱為無界面。面r的邊界長度稱為面r的度（degree）記為deg (r) ，又稱為面r的次數 。,2、面、邊界 定義7-5.2 設G=是一連通平面圖，G的邊將G所在的平面分成若干個區(qū)域，每個區(qū)域稱為G的一個面 (

4、regions) ，包圍該面的所有邊所構成的回路稱為這個面的邊界（boundary）。面積有限的區(qū)域稱為有界面（內部面），面積無限的區(qū)域稱為無界面（外部面）。面r的邊界長度稱為面r的度（degree）記為deg (r) ，又稱為面r的次數 。,例如圖7-5.3,deg(r1)=3 deg(r2)=3 deg(r3)=5 deg(r4)=4 deg(r5)=3,deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5) =18,如邊是兩個面的分界線，該邊在兩個面的度數中各記1次。如邊不是兩個面的分界線(稱為割邊)則該邊在該面的度數中重復記了兩次，故定理結論成立。,見前面的圖7

5、-5.3,3、定理7-5.1 設G為一有限平面圖，面的次數之和等于其邊數的兩倍。, 證明思路：任一條邊或者是兩個面的共同邊界（貢獻2次），或者是一個面的重復邊（貢獻2次） ,4、歐拉定理 定理7-5.2（歐拉定理） 設G為一平面連通圖，v為其頂點數，e為其邊數，r 為其面數，那么歐拉公式成立 v e + r = 2, 證明 （1）若G為一個孤立結點，則v=1，e=0，r=1， 故 v-e+r=2成立。,（2）若G為一個邊，即v=2，e=1，r=1， 則 v-e+r=2成立。,（3）設G為k條邊時，歐拉公式成立，即 vk-ek+rk=2?？疾霨為k+1條邊時的情況。,因為在k條邊的連通圖上增加一

6、條邊，使它仍為連通圖，只有下述兩種情況：,加上一個新結點b，b與圖上的一點a相連，此時vk和ek兩者都增加1，而面數rk沒變，故 （ vk +1）-（ ek +1）+ rk = vk-ek+rk=2。,用一條邊連接圖上的已知兩點，此時ek和rk都增加1，結點數vk沒變，故 vk -（ek +1）+（rk +1）=vk-ek+rk=2。 ,練習 317頁（1）,練習 317頁（6）,證明彼得森圖是非平面圖。,例：已知一個平面圖中結點數v=10，每個面均由4條邊圍成，求該平面圖的邊數和面數。,解：因每個面的次數均為4，則2e=4r，即e=2r，又v=10，代入歐拉公式v-e+r=2有10-2r+r

7、=2解得r=8，則e=2r=16。,說明：這是簡單連通平面圖的必要條件。,5、定理7-5.3 設G為一簡單連通平面圖，其頂點數v3，其邊數為e，那么 e3v 6, 證明思路：設G的面數為r,當v=3,e=2時上式成立,若e=3,則每一面的次數不小于3,各面次數之和為2e,因此 2e3r, r2e/3 代入歐拉公式: 2=v-e+rv-e+ 2e/3 整理后得: e3v 6 本定理的用途:判定某圖是非平面圖。,例如：K5中e=10，v=5，3v-6=9，從而e3v-6，所以K5不是平面圖。,定理7-5.3的條件不是充分的。如K3,3圖滿足定理7-5.3的條件（v=6，e=9，3v-6=12，e3

8、v-6成立），但K3,3不是平面圖。,315頁例2 證明K3,3圖不是平面圖。,在K3,3中任取三個結點，其中必有兩個結點不鄰接，故每個面的次數都不小于4， 由4r2e，re/2，即 v-e+e/2v-e+r=2， v-e/22， 2v- e 4， 2v-4e。,在給定圖G的邊上，插入一個新的度數為2的結點，使一條邊分成兩條邊，或者對于關于度數為2的結點的兩條邊，去掉這個結點，使兩條邊化成一條邊，這些都不會影響圖的平面性。,6、定義7-5.3 給定兩圖G1和G2，或者它們是同構的，或者反復地插入或去掉二度結點后， 使G1和G2同構，則稱G1和G2是在2度結點內同構的，也稱G1和G2是同胚的。,7、庫拉托夫斯基定理(Kuratowski定理) 定理7-5.4 一個圖是平面圖的充要條件是它不含與K5或K3，3在二度結點內同構的子圖。,歐拉公式有時可以用來判定某個圖是非平