chap13 平面圖

1、1第十三章第十三章 平面圖平面圖2圖中的邊不要交叉4實(shí)際中的很多問題都涉及到一個(gè)圖中的邊是否會交叉的問題。例如：單面印刷電路板，集成電路的布線，交通設(shè)計(jì)問題；等等。4由此便抽象出平面圖的概念：沒有交叉 (這里當(dāng)然不是指在端點(diǎn)處的相互鄰接）的邊的圖。4一個(gè)有交叉的邊的圖能不能轉(zhuǎn)換成與之同構(gòu)的平面圖，顯然是人們所關(guān)注的問題。4本章就是介紹平面圖以及平面圖的性質(zhì)。313.1 平面圖的概念4平面圖4定義13.1.1：設(shè)G是平面上由有限個(gè)點(diǎn)及以這些點(diǎn)為端點(diǎn)的有限條連續(xù)曲線所組成的圖形，如果G中任意兩條線最多只在它們的端點(diǎn)處相交，稱G為平面圖，否則稱為非平面圖。4下例中，圖不是平面圖， 和是平面圖。5可平

2、面圖4上例中的圖雖然不是平面圖，但是卻和圖和圖是同構(gòu)的，這樣的圖稱為可平面圖。4可平面圖：如果一個(gè)圖G與一個(gè)平面圖H同構(gòu)，稱G是可平面圖；而稱H是G的一個(gè)平面嵌入；否則稱為不可平面圖。4上例中的圖是可平面圖，圖和圖是圖的兩個(gè)平面嵌入?？善矫鎴D的例子6上面的都是可平面圖，下面的是它們的平面嵌入。上面的都是可平面圖，下面的是它們的平面嵌入。7平面圖的面4定義13.1.2：設(shè)G是一個(gè)平面圖，平面被G的邊所圍成的區(qū)域稱為面，這些邊稱為該面的邊界；其中有限區(qū)域?qū)?yīng)的面稱為內(nèi)部面，無限區(qū)域?qū)?yīng)的面稱為外部面(用f0表示)。4顯然，任何一個(gè)平面圖恰有一個(gè)外部面。4用G(p, q, r)表示一個(gè)p個(gè)頂點(diǎn)，q條

3、邊以及r個(gè)面的平面圖。4一個(gè)面 f 所包含的邊數(shù)稱為 f 的次數(shù)，記為d( f ) ，若邊為割邊，則計(jì)算兩次。8計(jì)算下圖中各面的次數(shù)：4d( f0 ) = 3 ; 4d( f1 ) = 5 。2431f1f0(a)f1f0(b)f24d( f0 ) = 8 ;4d( f1 ) = 3 ;4d( f2 ) = 3 .練一練4指出平面圖指出平面圖的面、面的邊界及的面、面的邊界及面的次數(shù)面的次數(shù)9e6e1e2e3e4e5e7e8e10e9f0f1f2f3f4d(f0)=6.d(f1)=5.d(f2)=3.d(f3)=3.d(f4)=3. 面的總次數(shù)為20，邊數(shù)為10，正好兩倍？！10面的總次數(shù)為邊數(shù)

4、的兩倍4定理13.1.1：對任何平面圖G(p,q,r) ,有 d( fi ) =2q ,(i =1 , 2 , ,r).4證明：由于G的每條非割邊恰屬于兩個(gè)面，所以，在計(jì)算這兩個(gè)面的次數(shù)時(shí)，該邊計(jì)算兩次，而割邊只屬于一個(gè)面，但由規(guī)定也計(jì)算了兩次，故上式成立，即所有面的總次數(shù)為邊數(shù)的兩倍。4對比：d( vi ) =2q，(i =1 , 2 , , p)，即所有頂點(diǎn)的總度數(shù)為邊數(shù)的二倍。11平面圖的同構(gòu)12圖的同構(gòu)與平面圖的同構(gòu)G12345H123456613外平面圖4定義13.1.4：圖G稱為外可平面圖，如果它有一個(gè)平面嵌入H，使得G的所有頂點(diǎn)均在H的同一個(gè)面的邊界上，這時(shí)，稱H為外平面圖。f1

5、f1這是外平面圖。這不是外平面圖。G:紅色頂點(diǎn)在外部面的紅色頂點(diǎn)在外部面的邊界上邊界上,藍(lán)色的在內(nèi)部面的藍(lán)色的在內(nèi)部面的H:所有點(diǎn)在外部面邊界上所有點(diǎn)在外部面邊界上14極大平面圖4定義13.1.5 設(shè)G是一個(gè)可平面圖，如果對G中任意兩個(gè)互不鄰接的頂點(diǎn)u , v , G+uv成為一個(gè) 不可平面圖，則稱G是一個(gè)極大可平面圖，極大可平面圖的一個(gè)平面嵌入稱為極大平面圖。4說明：對一個(gè)不是極大的可平面圖，可以添加一些邊以得到一個(gè)極大可平面圖。(如圖)15極大平面圖的面都是三角形4定理13.1.2 極大簡單平面圖的任何一個(gè)面都是三角形K3。 4證明： (反證)設(shè)G是極大簡單平面圖。若G的某個(gè)面 f 不是K

6、3，不妨設(shè) f 由閉途徑v1v2vnv1圍成，且d(f) = n 4。為簡單起見，不妨設(shè)n = 4，即f 由閉途徑v1v2v3v4v1圍成。則 f 只有以下三種情況：v1與v3不鄰接；v1與v3鄰接，而v2與 v4不鄰接； v1與v3鄰接，而v2與 v4也鄰接。4 下面我們對這三種情況分別予以討論：即每個(gè)面的次數(shù)均為即每個(gè)面的次數(shù)均為3。16極大平面圖的面都是三角形證明：若v1與v3不鄰接，則v1v2v3v4v1圍成內(nèi)部面，v1v2v3v4 于是在該面內(nèi)聯(lián) 結(jié)v1和v3不破壞G的平面性，此與G是極大簡單平面圖的假設(shè)矛盾；若v1與v3鄰接，v2與v4不鄰接，則v1v2v3 v1 圍成內(nèi)部面，邊v

7、1v4及頂點(diǎn)v4必在此面的外部，v1v2v3v4 故聯(lián)結(jié)v2和v4不破壞G的平面性，此與G的假設(shè)矛盾；17極大平面圖的面都是三角形證明：若v1與v3鄰接，且 v2與v4鄰接，則由于v1v2v3v4v1所圍成的區(qū)域是內(nèi)部面。v1v2v3v4 因此邊v1v3，v2v4都在此面之外，因而必相交, 此與G的可平面性矛盾。綜合以上，知結(jié)論成立。此定理可作為極大平面圖的判定定理。此定理可作為極大平面圖的判定定理。極大平面圖的判定4判斷下面各圖是否為極大平面圖判斷下面各圖是否為極大平面圖18G1G2G3 只有只有G3為極大平面圖。為極大平面圖。 因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為因?yàn)橹挥性搱D每個(gè)面的次數(shù)都為3。

8、1913.2 歐拉公式可平面性的必要條件4歐拉在研究凸多面體時(shí)得到了它們的頂點(diǎn)數(shù)、歐拉在研究凸多面體時(shí)得到了它們的頂點(diǎn)數(shù)、棱數(shù)和面數(shù)之間的一個(gè)簡單關(guān)系，將這個(gè)關(guān)系棱數(shù)和面數(shù)之間的一個(gè)簡單關(guān)系，將這個(gè)關(guān)系應(yīng)用到平面圖上，就有了歐拉公式。應(yīng)用到平面圖上，就有了歐拉公式。4本本節(jié)主要介紹若干可平面性的必要條件節(jié)主要介紹若干可平面性的必要條件2021 歐拉公式4定理13.2.1(歐拉公式)：任何一個(gè)簡單連通平面圖G (p, q, r)均滿足：p q + r = 2 .4證明：對面數(shù)r作歸納證明。 當(dāng)r=1時(shí)，G是樹，此時(shí)q = p 1，結(jié)論成立。 假設(shè)對G (p, q, r-1)， r2，結(jié)論成立，設(shè)

9、G是有r個(gè)面的平面圖，G至少有一條回路。設(shè)e是某回路上的邊，G e仍是連通平面圖，它有p個(gè)頂點(diǎn)，q 1條邊和r 1個(gè)面，由歸納假設(shè)有， p (q 1)+(r 1) = 2。整理即得 p q + r = 2。 由歸納法原理，歐拉公式成立。22面等次平面圖中邊與點(diǎn)的關(guān)系4推論13.2.1：若簡單平面圖G (p, q, r)的每個(gè)面的次數(shù)均為m , 則 q = m(p 2) / (m 2)4證明：由定理13.1.1，2q = d( fi ) = mr ，解出r，代入歐拉公式, 得 p q + (2/m)q = 2 整理上式即得證。23簡單平面圖邊數(shù)的上界4推論13.2.2 對任何簡單平面圖G (p,

10、 q, r) ( p 3) , q 3p 6 .4證明：由于極大簡單平面圖的每個(gè)面都是K3 ,故將 m = 3代入推論13.2.1中的式q = m(p 2) / (m 2) 有 q= 3(p 2) = 3p 6 . 故對一般簡單平面圖有q 3p 6 .24K5是不可平面圖4推論13.2.3 K5是不可平面圖。4證明：若K5是可平面圖，則由推論13.2.2知q 3p 6 ，于是 10 = q 3p 6 =35 6 = 9 , 即 ：10 9 ，矛盾。故結(jié)論成立。25無3次面的平面圖邊數(shù)的上界4推論13.2.4：若簡單平面圖G (p, q, r)的每個(gè)面均不是K3 ，則 q 2p 4 .4證明：由

11、假設(shè)每個(gè)面的次數(shù)不小于4。 2q = d( fi ) 4r4即 r q /2 ,從而由歐拉公式有 2 = p q + r p q + q /2 = p q /2 整理后得 q 2p 4 .26K3,3是不可平面圖4推論13.2.5：K3,3是不可平面圖。4證明：因K3,3是二分圖，故它不含K3 ，假設(shè)K3,3是可平面圖，則由推論13.2.4知 9 = q 2p 4 =26 4 = 8 , 即 ：9 8 ，矛盾。故結(jié)論成立。27簡單平面圖的最小度小于64推論13.2.6：任何簡單平面圖G (p, q, r)均有(G) 6。4證明：若(G) 6，則 4 q = (1/2) d( vi ) (2q

12、= d( vi ) )4 (1/2)p*(G) (6/2)p 3p 6 ,4此與推論13.2.2( 對任何簡單平面圖G (p, q, r) ( p 3)，都有 q 3p 6 )矛盾。故結(jié)論成立。小結(jié)：簡單平面圖的性質(zhì)4任何簡單連通平面圖任何簡單連通平面圖G(p,q,r)均滿足：均滿足：p-q+r=2（歐拉公式）（歐拉公式）4任何簡單平面圖任何簡單平面圖G(p,q,r)均滿足：均滿足：q3p-6 (G)6（重要的平面圖著色理論）（重要的平面圖著色理論）284K5、K3,3是不可平面圖是不可平面圖29極大平面圖的五個(gè)性質(zhì) 4定理13.2.2：設(shè)簡單平面圖G (p, q, r)是極大平面圖( p 4

13、) ，于是 q = 3p 6 ; r = 2p 4 ; (G) 3; (G) 3 ; G中至少有4個(gè)頂點(diǎn)的度不超過5 . 30極大平面圖的邊數(shù)4證明：由定理13.1.2(極大簡單平面圖的任何一個(gè)面都是三角形K3 ) ，將推論13.2.1中的式q = m(p 2) / (m 2)中的m用m=3 代入，即可得q = 3p 6 ;31極大平面圖的面數(shù)證明：由性質(zhì)有q = 3p 6 ，將其代入歐拉公式得： p q + r = p (3p 6) + r = 2 , 整理即得r = 2p 4 ；32極大平面圖連通度不小于34證明：G的面都是K3， (G) 2。4 假設(shè)(G) = 2 ，則有頂點(diǎn)割S =u,

14、 v。其中的u和v都應(yīng)該與G S的至少兩個(gè)連通分支中的頂點(diǎn)在G中鄰接。4不妨設(shè)在G的一個(gè)平面嵌入G 中與u鄰接的點(diǎn)按環(huán)繞u的順序依次為u1, , ut。4而 u1, , ut中除可能有一點(diǎn)是v外，其余的點(diǎn)分別屬于GS的至少兩個(gè)分支，必有兩點(diǎn)ui和ui+1分屬G S的兩個(gè)不同分支。33極大平面圖連通度不小于3圖示4圖示1uv分支1分支2S=u,vui+1ui+2.utui.u2u14圖示2uvG34極大平面圖連通度不小于34證明： S是頂點(diǎn)割，ui和ui+1分別屬于G S的兩個(gè)不同分支。uvui+1uif14由ui和ui+1的取法可知，在uui和uui+1之間沒有其它與u鄰接的邊，依據(jù)定理 13

15、.1.2，在G 中u uiui+1是一個(gè)K3面，故ui和ui+1鄰接。4從而在G S中， ui也和ui+1鄰接，這與S是頂點(diǎn)割相矛盾。所以 (G) 3。35極大平面圖最小度不小于3證明：由定理7.1.1可知圖的連通度不大于邊連通度，而邊連通度又不大于最小度，即(G) (G) (G) ；又由性質(zhì)即可得極大平面圖最小度不小于3，即(G) (G) 3 。36至少有4個(gè)頂點(diǎn)的度不超過5證明：設(shè)G的頂點(diǎn)集V = v1 , v2 , , vp。 若最多只有三個(gè)頂點(diǎn)的度不超過5，即對 i = 1, 2, , p 3，均有d(vi) 6，則由性質(zhì)， 對i = p2 , p1, p，有d(vi) (G) 3。

16、于是，6p 21= 2q 9？因?yàn)橛尚再|(zhì)，q = 3p 6 ，于是6p 12 = 2q 2q d( vj ) (這里j = p2, p-1, p) = d(vi ) (這里i =1, 2, , p 3) 6(p 3) = 6p 18 .此為矛盾，故結(jié)論成立。3713.3 可平面性判定38剖分圖4定義13.3.1：設(shè)G是一個(gè)圖，e = uv E(G)，在G uv中增加一個(gè)新點(diǎn)w及邊wu , wv .稱此過程為對圖G的一次剖分運(yùn)算。如果H是由G經(jīng)過有限次剖分運(yùn)算得到的，則稱H是G的剖分圖。4直觀地說，剖分就是在圖的某邊上加個(gè)頂點(diǎn)。4右邊就是K4的剖分。39可平面圖的充要條件4定理13.3.1 (K

17、uratowski定理) 一個(gè)圖是可平面圖的充分必要條件是它不包含K5或K3,3的剖分圖.4該定理亦可描述為：一個(gè)圖是可平面的當(dāng)且僅當(dāng)它沒有一個(gè)可以收縮到K5或K3,3的子圖。40Petersen圖的收縮和剖分Petersen圖4例如：Petersen圖不是可平面圖，因?yàn)樗蠯3,3的剖分。Petersen圖含有K3,3的剖分Petersen圖收縮為K5它也可以收縮為K5。4113.4 平面圖的面著色42給平面圖著色4對簡單圖G(p, q)只考慮頂點(diǎn)和邊，其著色也只有點(diǎn)著色和邊著色。4對簡單平面圖G (p, q, r)則還需要考慮面，其著色還有相應(yīng)的面著色。4平面圖著色的一個(gè)直接的重要的應(yīng)用

18、:地圖著色 。4用顏色來區(qū)分地圖中的區(qū)域，最少需要多少種顏色呢？這就是著名的四色問題。43面的鄰接4定義13.4.1：設(shè) f1 和 f2是平面圖G的兩個(gè)面。若 f1 和 f2的邊界至少有一條公共邊，則稱f1與 f2是鄰接的，否則稱 f1與 f2不鄰接。4區(qū)分三種鄰接： 點(diǎn)鄰接：兩個(gè)頂點(diǎn)有邊相關(guān)聯(lián)； 邊鄰接：兩條邊有共同的端點(diǎn)； 面鄰接：兩個(gè)面有共同的邊。44有公共頂點(diǎn)的面不是鄰接的面4注意：注意：兩個(gè)面如果在邊界上只有一個(gè)或有限個(gè)兩個(gè)面如果在邊界上只有一個(gè)或有限個(gè)公共點(diǎn)，則它們是不鄰接的公共點(diǎn)，則它們是不鄰接的。ABCDEFABCD4下下左圖中的面左圖中的面A與與E , A與與C , A與與D

19、都不是鄰都不是鄰接的面接的面。4下下右圖中的面右圖中的面A與與C，B與與D也都不是鄰接的也都不是鄰接的面。面。45面著色4定義13.4.2：設(shè)G是平面圖，S = 1, 2, , k，k1。若存在面集R(G)到S的滿射r，則稱r為G的k面著色，S為面色集。若對G中任意兩個(gè)鄰接面 f1和 f2 ，均有r(f1)r(f2)，則稱r是正常k面著色，并稱G是k面可著色的。圖G 的正常k面可著色中最小的k稱為G的面色數(shù)，記為*(G) 。4對比：色數(shù)(G) ：最小正常k(頂點(diǎn))著色； 邊色數(shù)(G) ：最小正常k邊著色； 面色數(shù)*(G) ：最小正常k面著色。46對偶圖4如果把每個(gè)面看作一個(gè)頂點(diǎn)，若兩個(gè)面的邊界

20、有一條公共邊，則看作兩個(gè)頂點(diǎn)之間有一條邊關(guān)聯(lián)。這樣就可以把一個(gè)平面圖G中面與面之間鄰接關(guān)系描述為另一個(gè)圖G*中頂點(diǎn)與頂點(diǎn)之間的鄰接關(guān)系。4這樣對一個(gè)平面圖G進(jìn)行轉(zhuǎn)換，所得到的圖G*稱為圖G的對偶圖4于是可將對平面圖G的面著色轉(zhuǎn)換為對其對偶圖G*的點(diǎn)著色問題。47對偶圖的構(gòu)造4對偶圖的構(gòu)造：在G的每個(gè)面內(nèi)放一個(gè)頂點(diǎn) f*，這些頂點(diǎn)就構(gòu)成了G*的頂點(diǎn)集V(G*)。 若G的兩個(gè)面 f 和g有一條公共邊e， 則畫一條以 f*和 g*為端點(diǎn)的邊e*， e*僅穿過e一次，對于G中僅屬于一個(gè)面的割邊e，則畫一條以 f*為端點(diǎn)的環(huán)，穿過e一次。4如果一個(gè)圖的對偶圖就是它自己，則稱為自對偶圖。48對偶圖的舉例自對偶圖49G與G*的關(guān)系4對任何一個(gè)平面圖G，G*是唯一確定的：p(G*) = r(G) , q(G*) = q(G) ;G*中的頂點(diǎn) f* 和 g* 鄰接當(dāng)且僅當(dāng)G中與 f* 和 g*對應(yīng)的兩個(gè)面 f 和 g 鄰接；G*有多重邊當(dāng)且僅當(dāng)G的某兩個(gè)面至少有兩條公共邊；G*有環(huán)當(dāng)且僅當(dāng)G中有割邊。4可將對平面圖G的面著色轉(zhuǎn)換為對其對偶圖G*的點(diǎn)著色問題：(G*) = *(G)。50四色問題4稱無割邊的平面圖為平面地圖。顯然，有割邊的平面圖