離散數(shù)學(xué)平面圖省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

第17章平面圖離散數(shù)學(xué)中國(guó)地質(zhì)大學(xué)本科生課程1/47本章說(shuō)明本章主要內(nèi)容平面圖基本概念歐拉公式平面圖判斷平面圖對(duì)偶圖2/47本章所包括到圖均指無(wú)向圖。3/4717.1平面圖基本概念17.2歐拉公式17.3平面圖判斷17.4平面圖對(duì)偶圖

本章小結(jié)

習(xí)題

作業(yè)4/4717.1平面圖基本概念一、關(guān)于平面圖一些基本概念1、平面圖定義定義17.1

G可嵌入曲面S——假如圖G能以這么方式畫(huà)在曲面S上，即除頂點(diǎn)處外無(wú)邊相交。

G是可平面圖或平面圖——若G可嵌入平面。G平面嵌入——畫(huà)出無(wú)邊相交平面圖。非平面圖——無(wú)平面嵌入圖。5/47（2）是（1）平面嵌入，（4）是（3）平面嵌入。6/472、幾點(diǎn)說(shuō)明及一些簡(jiǎn)單結(jié)論普通所談平面圖不一定是指平面嵌入，但討論一些性質(zhì)時(shí)，一定是指平面嵌入。K5和K3,3都不是平面圖。定理17.1

設(shè)G

G，若G為平面圖，則G

也是平面圖。設(shè)G

G，若G

為非平面圖，則G也是非平面圖。由定理可知，

Kn(n

5)和K3,n(n

3)都是非平面圖。定理17.2

若G為平面圖，則在G中加平行邊或環(huán)所得圖還是平面圖。

即平行邊和環(huán)不影響圖平面性。7/47二、平面圖面與次數(shù)（針對(duì)平面圖平面嵌入）1、定義定義17.2設(shè)G是平面圖，G面——由G邊將G所在平面劃分成每一個(gè)區(qū)域。無(wú)限面（外部面）——面積無(wú)限面，記作R0。有限面（內(nèi)部面）——面積有限面，記作R1,R2,…,Rk。面Ri邊界——包圍面Ri全部邊組成回路組。面Ri次數(shù)——Ri邊界長(zhǎng)度，記作deg(Ri)。8/472、幾點(diǎn)說(shuō)明若平面圖G有k個(gè)面，可籠統(tǒng)地用R1,R2,…,Rk表示，不需要指出外部面?；芈方M是指：邊界可能是初級(jí)回路（圈），可能是簡(jiǎn)單回路，也可能是復(fù)雜回路。尤其地，還可能是非連通回路之并。平面圖有4個(gè)面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。R1R2R3R09/47定理17.3

平面圖G中全部面次數(shù)之和等于邊數(shù)m兩倍，即本定理中所說(shuō)平面圖是指平面嵌入。

e∈E(G)，當(dāng)e為面Ri和Rj(i≠j)公共邊界上邊時(shí)，在計(jì)算Ri和Rj次數(shù)時(shí)，e各提供1。

當(dāng)e只在某一個(gè)面邊界上出現(xiàn)時(shí)，則在計(jì)算該面次數(shù)時(shí)，e提供2。于是每條邊在計(jì)算總次數(shù)時(shí)，都提供2，因而deg(Ri)=2m。證實(shí)10/47三、極大平面圖1、定義定義17.3若在簡(jiǎn)單平面圖G中任意兩個(gè)不相鄰頂點(diǎn)之間加一條新邊所得圖為非平面圖，則稱G為極大平面圖。注意：若簡(jiǎn)單平面圖G中已無(wú)不相鄰頂點(diǎn)，G顯然是極大平面圖，如K1（平凡圖）,K2,K3,K4都是極大平面圖。2、極大平面圖主要性質(zhì)定理17.4

極大平面圖是連通，而且n(n

3)階極大平面圖中不可能有割點(diǎn)和橋。11/47定理17.5

設(shè)G為n(n

3))階簡(jiǎn)單連通平面圖，G為極大平面圖當(dāng)且僅當(dāng)G每個(gè)面次數(shù)均為3。本節(jié)只證實(shí)必要性，即設(shè)G為n(n

3))階簡(jiǎn)單連通平面圖，G為極大平面圖，則G每個(gè)面次數(shù)均為3。因?yàn)閚

3,又G必為簡(jiǎn)單平面圖，可知，G每個(gè)面次數(shù)均

3。因?yàn)镚為平面圖，又為極大平面圖?？勺CG不可能存在次數(shù)>3面。證實(shí)思緒12/47假設(shè)存在面Ri次數(shù)deg(Ri)=s≥4，如圖所表示。在G中，若v1與v3不相鄰，在Ri內(nèi)加邊(v1,v3)不破壞平面性，這與G是極大平面圖矛盾，因而v1與v3必相鄰，因?yàn)镽i存在，邊(v1,v3)必在Ri外。類似地，v2與v4也必相鄰，且邊(v2,v4)也必在Ri外部，于是必產(chǎn)生(v1,v3)與(v2,v4)相交于Ri外部，這又矛盾于G是平面圖，所以必有s＝3，即G中不存在次數(shù)大于或等于4面，所以G每個(gè)面為3條邊所圍，也就是各面次數(shù)均為3。sS-113/47只有右邊圖為極大平面圖。因?yàn)橹挥性搱D每個(gè)面次數(shù)都為3。14/47四、極小非平面圖定義17.4若在非平面圖G中任意刪除一條邊，所得圖G

為平面圖，則稱G為極小非平面圖。由定義不難看出：K5,K3,3都是極小非平面圖。極小非平面圖必為簡(jiǎn)單圖。比如：以下各圖均為極小非平面圖。小節(jié)結(jié)束15/4717.2歐拉公式

一、歐拉公式相關(guān)定理1、

歐拉公式定理17.6

對(duì)于任意連通平面圖G，有

n-m+r=2

其中，n、m、r分別為G頂點(diǎn)數(shù)、邊數(shù)和面數(shù)。證實(shí)對(duì)邊數(shù)m作歸納法。(1)m＝0時(shí)，因?yàn)镚為連通圖，所以G只能是由一個(gè)孤立頂點(diǎn)組成平凡圖，即n=1，m=0，r=1，結(jié)論顯然成立。(2)m＝1時(shí)，因?yàn)镚為連通圖，所以n=2，m=1，r=1，結(jié)論顯然成立。16/47(3)設(shè)m＝k(k≥1)時(shí)成立，當(dāng)m＝k+1時(shí)，對(duì)G進(jìn)行以下討論。若G是樹(shù)，則G是非平凡，因而G中最少有兩片樹(shù)葉。設(shè)v為樹(shù)葉，令G'=G-v，則G'依然是連通圖，且G'邊數(shù)m'=m-1=k，n'=n-1，r'=r。由假設(shè)可知n'-m'+r'=2，式中n'，m'，r'分別為G'頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。于是n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2若G不是樹(shù)，則G中含圈。設(shè)邊e在G中某個(gè)圈上，令G'=G-e，則G'仍連通且m'=m-1=k，n'=n，r'=r-1。由假設(shè)有n'-m'+r'=2。于是n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=217/47定理17.7

對(duì)于含有k(k≥2)個(gè)連通分支平面圖G，有

n-m+r=k+1

其中n，m，r分別為G頂點(diǎn)數(shù)，邊數(shù)和面數(shù)。證實(shí)設(shè)G連通分支分別為G1、G2、…、Gk，并設(shè)Gi頂點(diǎn)數(shù)、邊數(shù)、面數(shù)分別為ni、mi、ri、i=1，2，…，k。由歐拉公式可知:ni-mi+ri=2，i=1，2，…，k (17.1)易知，因?yàn)槊總€(gè)Gi有一個(gè)外部面，而G只有一個(gè)外部面，所以G面數(shù)于是，對(duì)(17.1)兩邊同時(shí)求和得

經(jīng)整理得n-m+r=k+1。18/472、與歐拉公式相關(guān)定理定理17.8

設(shè)G為連通平面圖，且每個(gè)面次數(shù)最少為l(l3)，則G邊數(shù)與頂點(diǎn)數(shù)有以下關(guān)系：由定理17.3（面次數(shù)之和等于邊數(shù)2倍）及歐拉公式得證實(shí)解得19/47推論

K5,K3,3不是平面圖。證實(shí)若K5是平面圖，因?yàn)镵5中無(wú)環(huán)和平行邊，所以每個(gè)面次數(shù)均大于或等于l≥3，由定理17.8可知邊數(shù)10應(yīng)滿足10≤(3/(3-2))(5-2)=9這是個(gè)矛盾，所以K5不是平面圖。若K3,3是平面圖，因?yàn)镵3,3中最短圈長(zhǎng)度為l≥4，于是邊數(shù)9應(yīng)滿足9≤(4/(4-2))(6-2)=8這又是矛盾，所以K3,3也不是平面圖。20/47定理17.9

設(shè)G是有k(k≥2)個(gè)連通分支平面圖，各面次數(shù)最少為l(l≥3)，則邊數(shù)m與頂點(diǎn)數(shù)n應(yīng)有以下關(guān)系：

定理17.10

設(shè)G為n(n

3)階m條邊簡(jiǎn)單平面圖，則m

3n

6。設(shè)G有k(k

1)個(gè)連通分支，若G為樹(shù)或森林，當(dāng)n

3時(shí)，m=n-k

3n

6為真。若G不是樹(shù)也不是森林，則G中必含圈，又因?yàn)镚是簡(jiǎn)單圖，所以，每個(gè)面最少由l（l

3）條邊圍成，又在l=3到達(dá)最大值，由定理17.9可知證實(shí)21/47定理17.11

設(shè)G為n(n

3)階m條邊極大平面圖，則m=3n

6。證實(shí)因?yàn)闃O大平面圖是連通圖，由歐拉公式得:

r=2+m-n (17.4)又因?yàn)镚是極大平面圖，由定理17.7必要性可知，G每個(gè)面次數(shù)均為3，所以：將(17.4)代入(17.5)，整理后得m=3n-6。22/47二、一個(gè)意義重大定理定理17.12

設(shè)G為簡(jiǎn)單平面圖，則G最小度

(G)

5。若階數(shù)n

6，結(jié)論顯然成立。若階數(shù)n

7時(shí)，用反證法。假設(shè)

(G)

6，由握手定理可知：證實(shí)因而m

3n，這與定理17.10矛盾。所以，假設(shè)不成立，即G最小度

(G)

5。本定理在圖著色理論中占主要地位。說(shuō)明23/47一、為判斷定理做準(zhǔn)備1、插入2度頂點(diǎn)和消去2度頂點(diǎn)定義17.5

設(shè)e=(u,v)為圖G一條邊，在G中刪除e，增加新頂點(diǎn)w，使u、v均與w相鄰，稱為在G中插入2度頂點(diǎn)w。設(shè)w為G中一個(gè)2度頂點(diǎn)，w與u、v相鄰，刪除w，增加新邊(u,v)，稱為在G中消去2度頂點(diǎn)w。17.3平面圖判斷24/472、圖之間同胚若兩個(gè)圖G1與G2同構(gòu)，或經(jīng)過(guò)重復(fù)插入或消去2度頂點(diǎn)后是同構(gòu)，則稱G1與G2是同胚。上面兩個(gè)圖分別與K3,3,K5同胚。25/47二、兩個(gè)判斷定理定理17.13(庫(kù)拉圖斯基定理1)圖G是平面圖當(dāng)且僅當(dāng)G中既不含與K5同胚子圖，也不含與K3,3同胚子圖。定理17.14(庫(kù)拉圖斯基定理2)圖G是平面圖當(dāng)且僅當(dāng)G中既沒(méi)有能夠收縮到K5子圖，也沒(méi)有能夠收縮到K3,3子圖。26/47例17.1證實(shí)彼得松圖不是平面圖。將彼得松圖頂點(diǎn)標(biāo)次序，見(jiàn)圖(1)所表示。證實(shí)還能夠這么證實(shí)：用G表示彼得松圖，令G'=G-{(j,g),(c,d)}G‘如圖(3)所表示，易知它與K3,3同胚，在圖中將邊(a,f),(b,g),(c,h),(d,i),(e,j)收縮，所得圖為圖(2)所表示，它是K5，由定理17.16可知，彼得松圖不是平面圖。由定理17.15可知，G為非平面圖。27/47例17.2對(duì)K5插入2度頂點(diǎn)，或在K5外放置一個(gè)頂點(diǎn)使其與K5上若干頂點(diǎn)相鄰，共可產(chǎn)生多少個(gè)6階簡(jiǎn)單連通非同構(gòu)非平面圖？用插入2度頂點(diǎn)方法只能產(chǎn)生一個(gè)非平面圖，如圖(1)所表示。解答在K5外放置一個(gè)頂點(diǎn)，使其與K5上1個(gè)到5個(gè)頂點(diǎn)相鄰，得5個(gè)圖，如圖(2)到(6)所表示。它與K5同胚，所以是非平面圖。它們都含K5為子圖，由庫(kù)拉圖斯基定理可知，它們都是非平面圖，而且也滿足其它要求。28/47例17.3由K3,3加若干條邊能生成多少個(gè)6階連通簡(jiǎn)單非同構(gòu)非平面圖？對(duì)K3,3加1～6條邊所得圖都含K3,3為子圖，由庫(kù)拉圖斯基定理可知，它們都是非平面圖。在加2條、加3條、加4條邊時(shí)又各產(chǎn)生兩個(gè)非同構(gòu)非平面圖，連同K3,3本身共有10個(gè)滿足要求非平面圖。其中，綠線邊表示后加新邊。解答小節(jié)結(jié)束29/4717.4平面圖對(duì)偶圖一、對(duì)偶圖定義定義17.6

設(shè)G是某平面圖某個(gè)平面嵌入，結(jié)構(gòu)G對(duì)偶圖G*以下：在G面Ri中放置G*頂點(diǎn)vi*。設(shè)e為G任意一條邊，

若e在G面Ri與Rj公共邊界上，做G*邊e*與e相交，且e*關(guān)聯(lián)G*位于Ri與Rj中頂點(diǎn)vi*與vj*，即e*=(vi*,vj*)，e*不與其它任何邊相交。

若e為G中橋且在面Ri邊界上，則e*是以Ri中G*頂點(diǎn)vi*為端點(diǎn)環(huán)，即e*=(vi*,vi*)。30/47實(shí)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖。31/47從定義不難看出G對(duì)偶圖G*有以下性質(zhì)：G*是平面圖，而且是平面嵌入。G*是連通圖。若邊e為G中環(huán)，則G*與e對(duì)應(yīng)邊e*為橋，若e為橋，則G*中與e對(duì)應(yīng)邊e*為環(huán)。在多數(shù)情況下，G*為多重圖（含平行邊圖）。同構(gòu)平面圖（平面嵌入）對(duì)偶圖不一定是同構(gòu)。32/47二、平面圖與對(duì)偶圖階數(shù)、邊數(shù)與面數(shù)之間關(guān)系。定理17.15

設(shè)G*是連通平面圖G對(duì)偶圖，n*、m*、r*和n、m、r分別為G*和G頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則（1）n*=r（2）m*=m（3）r*=n（4）設(shè)G*頂點(diǎn)v*i位于G面Ri中，則dG*(vi*)=deg(Ri)33/47(1)、(2)由G*結(jié)構(gòu)可知是顯然。(3)因?yàn)镚與G*都連通，因而滿足歐拉公式:

n-m+r=2

n*-m*+r*=2 由(1)、(2))可知，r*=2+m*-n*=2+m-r=n(4)設(shè)G面Ri邊界為Ci，設(shè)Ci中有k1(k1≥0)條橋，k2個(gè)非橋邊，于是

Ci長(zhǎng)度為k2+2k1，即deg(Ri)＝k2+2k1，k1條橋?qū)?yīng)vi*處有k1個(gè)環(huán)，k2條非橋邊對(duì)應(yīng)從vi*處引出k2條邊，所以dG*(vi*)＝k2+2k1＝deg(Ri)。證實(shí)34/47定理17.16

設(shè)G*是含有k（k

2）個(gè)連通分支平面圖G對(duì)偶圖，n*,m*,