第五章圖論（六）-read

1、第五章 圖論,5.6平面圖5.6.1平面圖的概念例 考慮把三座房和三種設(shè)施每種都連接起來的問題，如圖7-64所示，是否有可能使得這樣的連接里不發(fā)生交叉？這個問題可以用完全偶圖K3,3來建模。原來的問題可以重新敘述為：能否在平面里畫出K3,3，使得沒有兩條邊發(fā)生交叉？,印刷線路板的設(shè)計問題 定義1 圖的平面表示：圖的一種圖形表示（畫法），其中邊僅在頂點處相交平面圖：有平面表示的圖例1 判斷

2、下面的三個圖是否為平面性的。（接下頁）,解：K4是平面性的，因為可以不帶交叉地畫出它（圖7-66所示）；Q3是平面性的（圖7-68所示）；在平面里畫出K3,3而沒有邊交叉，任何這樣的嘗試都注定是失敗的。在K3,3的任何平面表示里，頂點v1和v2都必須同時與v4和v5連接。這四條邊所形成的封閉曲線把平面分割成兩個區(qū)域R1和R2，如圖7-70a）所示。頂點v3屬于R1或R2。當v3屬于閉曲線的內(nèi)部R2時，在v3和

3、v4之間以及在v3和v5之間的邊，把R2分割成兩個區(qū)域R21和R22，如圖7-70b）所示。,定義 在平面圖的一個平面表示中，邊把平面劃分成若干區(qū)域 面R：內(nèi)部不含圖的邊或頂點的、由邊所包圍的區(qū)域面的邊界： 包圍面的最短的回路面的度deg(R)：邊界的長度有限面：面積有限的面，無限面：面積無限的面例 右面的平面圖有3個面，R1和R2是有限面，R3是無限面R1的邊界：1231，R2的邊界：2342，R3的邊

4、界：1245431 deg(R1)=3，deg(R2)=3，deg(R3)=6R3的邊界不是12431，因為12431所包圍的區(qū)域含有邊，不能構(gòu)成面R2的邊界不是234542，因為234542不是包圍R2的最短的回路,定義 設(shè)平圖G=(V，E)有r個面，n個頂點，m條邊，稱用如下的方法構(gòu)造出來的圖 G*=(V*，E*)為G的對偶圖：(1) 在G的任意一個面Ri中取一個點作為G*的一個頂點Vi*，令V * =

5、{V1*，V2* ，…， Vr*}。(2) 對G的任意一條邊ek，若ek出現(xiàn)在G的兩個不同的面Ri和Rj( i??j) 的邊界中,則構(gòu)作G*的邊={Vi* ， Vj*}；若ek僅出現(xiàn)在G的某一個面Ri的邊界中,則構(gòu)作G*的邊(環(huán)) ek* ={Vi* ， Vi*}；令E*={e1* ， e2* ，…， em* }。,例 在G的無限面內(nèi)，僅有G*的一個頂點v4*，過v4*有G*的一個環(huán) 若平面圖G=(V，E)有n個頂點，m條邊

6、，r個面，則其對偶圖G* =(V* ，E*)（１）有r個頂點，m條邊（２）是平面圖（３）是連通圖（４）對于G的任意一個面R及R所對應(yīng)的G*的頂點V* ，deg(R)=d(V*)定理 平面圖的面的度數(shù)之和等于其邊的數(shù)目的兩倍。證明： 設(shè)可平面圖G=(V，E) ，其對偶圖G* =(V*,E*)，則 = =2|E*| (由握手定

7、理) =2|E|,,,5.6.2歐拉公式定理1 歐拉公式 連通平面圖，r=e-v+2。證明：直觀描述首先規(guī)定G的平面表示。將要這樣證明定理：構(gòu)造一系列子圖G1，G2，…，Ge=G，相繼地在每個階段上添加一條邊。用下面的歸納定義來這樣做。任意地選擇一條G的邊來獲得G1。從Gn-1這樣獲得Gn：任意地添加一條與Gn-1里頂點相關(guān)聯(lián)的邊，若與這條邊關(guān)聯(lián)的另一個頂點還不在Gn-1里，則添加這個頂點。這樣的構(gòu)造是可能

8、的，因為G是連通的。在添加e條邊之后就獲得G。設(shè)rn，en和vn分別表示G的平面表示所誘導出的Gn的平面表示的區(qū)域數(shù)、邊數(shù)和頂點數(shù)。現(xiàn)在通過歸納來進行證明。對G1來說關(guān)系r1=e1-v1+2為真。(接下頁),現(xiàn)在假定rn=en-vn+2。設(shè)｛an+1，bn+1｝是為了獲得Gn+1而添加到Gn里的邊。有兩種情形需要考慮。在第一種情形里，an+1和bn+1都已經(jīng)在Gn里了。這兩個頂點必然是在一個公共區(qū)域R的邊界上，否則就不可能把邊

9、｛an+1，bn+1｝添加到Gn里而沒有兩條邊交叉（并且Gn+1是平面性的。）這條新邊的添加把R分割成兩個區(qū)域。所以，在這種情形里，rn+1=rn+1, en+1=en+1，而且vn+1=vn+1 。因此，聯(lián)系著區(qū)域數(shù)、邊數(shù)、頂點數(shù)的公式兩邊都恰好增加一，所以這個公式仍然為真。在圖7-73 a）里說明這種情形。在第二種情形里，新邊的兩個頂點之一已不在Gn里。假定an+1在Gn里但是bn+1不在Gn里。添加這條新邊不產(chǎn)生任何新的區(qū)域

10、，因為bn+1必然是在邊界上有an+1的一個區(qū)域里。所以，rn+1=rn,，另外en+1=en+1，而且vn+1=vn+1。聯(lián)系著區(qū)域數(shù)、邊數(shù)、頂點數(shù)的公式兩邊都保持相等，所以這個公式仍然為真。在圖7-73 b）里說明這種情形。已經(jīng)完成了歸納論證。因此對所有n來說都有rn=en-vn+2。因為原圖是在添加了e條邊之后所獲得的圖Gn，所以這個定理為真。(見下頁圖),例4 假設(shè)連通圖平面性簡單圖有20個頂點，每個頂點的度都是3。這個

11、平面性圖的平面表示把平面分割成多少個區(qū)域？解 這個圖有20個頂點，每個頂點的度都是3，所以v=20。因為這些頂點的度之和3v=3*20=60是等于邊數(shù)的兩倍2e，所以有2e=60，即e=30。所以，根據(jù)歐拉公式，區(qū)域數(shù)是：r=e-v+2=30-20+2=12,推論1 簡單連通平面圖,v≥3，則e≤3v-6證明：①?deg(R)=2e ②簡單圖中，deg(R)≥3r 畫在平面里的連通平

12、面性簡單圖把平面分割成區(qū)域，比如說r個區(qū)域，每個區(qū)域的度數(shù)至少為3（簡單圖）。特別是，注意無界區(qū)域的度數(shù)至少為3，因為在圖中至少有3個頂點。 注意個區(qū)域的度數(shù)之和恰好是圖中邊數(shù)的兩倍，因為每條邊都在區(qū)域的邊界上出現(xiàn)兩次（或者在兩個不同區(qū)域里，或者兩次在相同的區(qū)域里）。因為每個區(qū)域都有大于等于3的度數(shù)，所以 2e=?deg(R)≥3r因此 (2/3)e≥r利用歐拉公式r=e-v+2，就得到

13、(2/3)e≥e-v+2所以得到v-2≥e/3。這樣就證明了e≤3v-6。,例5 證明K5不是平面圖 證明： 圖K5有5個頂點和10條邊。不過，對這個圖來說，不滿足不等式e≤3v-6，因為e=10和3v-6=9。因此， K5不是平面圖。推論2 簡單連通平面圖,v≥3，沒有長度為3的回路，則e≤2v-4證明：①?deg(R)=2e ②deg(R)≥4 推論2的證明類似于推論1的證明

14、，不同之處在于，在這種情形里，沒有長度為3的回路的事實蘊含著區(qū)域的度數(shù)至少為4。(接下頁),畫在平面里的連通平面性簡單圖把平面分割成區(qū)域，比如說r個區(qū)域，每個區(qū)域的度數(shù)至少為3（簡單圖）。又因為沒有長度為3的回路，所以每個區(qū)域的度數(shù)至少為4。 每個區(qū)域的度數(shù)之和恰好是圖中邊數(shù)的兩倍，因為每條邊都在區(qū)域的邊界上出現(xiàn)兩次。因為每個區(qū)域都有大于等于4的度數(shù)，所以 2e=?deg(R)≥4r因此 e≥2r利

15、用歐拉公式r=e-v+2，就得到 e≥2e-2v+4這樣就證明了e≤2v-4。例6 證明K3,3不是平面圖 證明： 因為K3,3沒有長度為3的回路（因為它是偶圖），所以可以使用推論2。 K3,3有6個頂點和9條邊。因為e=9和2v-4=8，所以推論2證明K3,3不是平面圖。,5.6.3 庫拉圖斯基定理定義 初等細分：在邊上插入頂點 收縮：合并頂點 圖同胚：能通過初等細分或（和）收縮轉(zhuǎn)換

16、例 (2)是的(1) 初等細分，(4)是(3)的收縮,定理2 庫拉圖斯基定理 圖是非平面圖??同胚于K3,3或K5的子圖。證明： 顯然，一個包含著同胚于K3,3或K5的子圖是非平面性的。不過，相反的命題——即每個非平面性圖都包含一個同胚于K3,3或K5的子圖的子圖——的證明是復雜的，因而不在這里給出。,例7 確定圖7-76中所示的圖是否為平面性的。 解： G有同胚于K5的子圖H。H是這樣獲得的：刪除h，

17、 j 和k 以及所有與這些頂點關(guān)聯(lián)的邊。H是同胚于K5的，因為從K5（帶有頂點a, b, c, g和i）通過一系列初等細分，添加頂點d, e 和f就可以獲得H。因此，G是非平面性的,習題 1.假定一個平面性圖有k個連通分支、e條邊和v個頂點。另外假設(shè)這個圖的平面表示把平面分割成r個區(qū)域。求用e，v，k所表示的r的公式。2.用庫拉圖斯基定理來確定下面所給的圖是否為平面性的。3.證明：若G是一個帶有v個頂點和e條邊的連