第十章-平面圖

第十章平面圖平面圖與平面嵌入平面圖的面、有限面、無限面面的次數(shù)極大平面圖極小非平面圖歐拉公式平面圖的對偶圖

1

10.1平面圖的概念

PlanarGraphs2例：有六個頂點(diǎn)的圖如上，試問：能否轉(zhuǎn)變成與其等價的，但沒有任何相交線的平面上的圖？結(jié)論：不能

3

問題：假定有三個倉庫x1，x2，x3和三個車站y1，y2，y3。為了便于貨物運(yùn)輸，準(zhǔn)備在倉庫與車站間修筑鐵路，如圖(a)所示,其中邊代表鐵路。問是否存在一種使鐵路不交叉的路線設(shè)計方案，以避免修建立交橋。

問題的解答但如果在x3與y1之間也要修一條鐵路，則可驗(yàn)證滿足要求的方案不存在。

x1

x2x3y1

y2y3(a)

x1

x2x3

y1

y2y3?4五宮修路問題相傳古代有一位獨(dú)裁者，臨死時留有遺囑，把土地分給他的五個兒子，這五個兒子在自己的領(lǐng)地上各修筑了一座宮殿，他們還企圖修一些道路，使得每兩座宮殿之間有一條道路直接相通，又要求道路不能交叉。結(jié)果，這五個愚蠢的王子煞費(fèi)苦心，終告失敗。

1930年，波蘭數(shù)學(xué)家Kuratowski給出平面圖的充要條件，嚴(yán)格證明了五宮修路問題是無解的。5平面圖和平面嵌入

定義如果能將圖G除頂點(diǎn)外邊不相交地畫在平面上,則稱G是平面圖.這個畫出的無邊相交的圖稱作G的平面嵌入.例如下圖中(1)~(4)是平面圖,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面圖.6定理1圖G可嵌入球面

圖G可嵌入平面。例1Q3是否可平面性？樹是一類重要的平面圖。應(yīng)用舉例：印刷電路版、集成電路設(shè)計。7例1=平面圖可平面圖8例：9可平面圖不可平面圖=不可平面圖

=10可平面圖==可平面圖1112平面圖和平面嵌入(續(xù))今后稱一個圖是平面圖,可以是指定義中的平面圖,又可以是指平面嵌入,視當(dāng)時的情況而定.當(dāng)討論的問題與圖的畫法有關(guān)時,是指平面嵌入.K5和K3,3是非平面圖設(shè)G

G,若G為平面圖,則G

也是平面圖;若G

為非平面圖,則G也是非平面圖.Kp(p5),K3,p(p3)都是非平面圖.平行邊與環(huán)不影響圖的平面性.K5K3,313定理若G是平面圖，則G中增加平行邊或環(huán)后所得的圖還是平面圖。本定理說明重邊與環(huán)不影響圖的平面性，因此研究圖的平面性時，不考慮重邊和環(huán)。14

定義：設(shè)G是一個平面圖，G將所嵌入的平面劃分為若干個區(qū)域，每個區(qū)域的內(nèi)部連同邊界稱為G的面，無界的區(qū)域稱為外部面或無限面。每個平面圖有且僅有一個外部面。設(shè)f是G的一個面，構(gòu)成f的邊界的邊數(shù)（割邊計算兩次）稱為f的次數(shù)，記為deg(f)。15例2下邊2個圖是同一個平面圖的平面嵌入.其實(shí),在平面嵌入中可把任何面作為外部面.f3f2f1（1）f1（2）f316例2

有5個面：f1，f2，f3，f4，f5

（f5為外部面）圖不連通，其外部面的次數(shù)為5f1f2f3f5f4deg(f1)=1deg(f2)=2deg(f3)=3deg(f4)=6deg(f5)=10相加為22，正好是邊數(shù)11的2倍17各域的邊界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1v2R1R2R0v1v3v4v5v6v7R318平面圖的面與次數(shù)(續(xù))f0f3fgf2f1acdeb例1右圖有4個面,deg(f1)=1,deg(f2)=3,deg(f3)=2,deg(f0)=8.19adcbr1eihgjr2r3f2021定理

設(shè)G=

V,E

是有限平面圖，有f個面，q條邊，則所有面的次數(shù)之和等于邊數(shù)的2倍。即=2|q|

證明：G的任何一邊，或者是兩個面的公共邊界，為每一個面的次數(shù)增加1；或者在一個面中作為邊界重復(fù)計算兩次，為該面的次數(shù)增加2。無論那種情況G的任何一邊為圖中面的次數(shù)和增加2，故所有面的次數(shù)之和等于邊數(shù)的2倍。22極大平面圖

定義若G是簡單平面圖,并且在任意兩個不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖,則稱G為極大平面圖.性質(zhì)若簡單平面圖中已無不相鄰頂點(diǎn)，則是極大平面圖.如

K1,K2,K3,K4都是極大平面圖.極大平面圖必連通.階數(shù)大于等于3的極大平面圖中不可能有割點(diǎn)和割邊.設(shè)G為p(p3)階極大平面圖,則G每個面的次數(shù)均為3.任何p(p

4)階極大平面圖G均有δ(G)

3.23實(shí)例3個圖都是平面圖,但只有右邊的圖為極大平面圖.24極小非平面圖

定義若G是非平面圖,并且任意刪除一條邊所得圖都是平面圖,則稱G為極小非平面圖.說明:K5,K3,3都是極小非平面圖極小非平面圖必為簡單圖下面4個圖都是極小非平面圖25

1750年瑞士的數(shù)學(xué)家列昂哈德?歐拉(LeophafdEuler)發(fā)現(xiàn)任何一個凸多面體，若有p個頂點(diǎn)，q條棱和f個面，總有p-q+f=2成立。我們將這個結(jié)論推廣到平面圖中，總結(jié)成如下的定理：

p-q+f=2V-E+F=2歐拉公式

26定理

(歐拉公式)設(shè)G為p階q條邊f(xié)個面的連通平面圖，則

p

q+f=2.證明：對邊數(shù)q做歸納證明.

⑴設(shè)q=0，由于G是連通圖，所以G只能為只有一個頂點(diǎn)的平凡圖（否則G

將不連通）,這時，p=1，q=0，f=1，p-q+f=2成立,結(jié)論為真.⑵設(shè)q=k(k≥1)時歐拉公式成立，下證當(dāng)q=k+1時歐拉公式也成立。分情況討論如下:

27（1）若G中無圈,則G為無圈連通圖，是一顆樹，必有一個度數(shù)為1的頂點(diǎn)v,刪除v及與它關(guān)聯(lián)的邊,記作G

.G

連通無圈,有p-1個頂點(diǎn),q-1條邊和f個面.由歸納假設(shè),(p-1)-（q-1）+f=2,即p-q+f=2,得證q=k+1時結(jié)論成立.(2)若G中有圈,則刪去一個圈上的一條邊,記作G

.G

連通,有p個頂點(diǎn),q-1條邊和f-1個面.由歸納假設(shè),

p-（q-1）+（f-1）=2,即p-q+f=2,得證.證畢.28去掉的這條邊需要考慮是兩個內(nèi)部面的邊界還是一個內(nèi)部面和一個外部面的邊界，無論哪種情況，面的個數(shù)和邊的個數(shù)都各減少1，頂點(diǎn)個數(shù)不變，假設(shè)仍成立。f3f2f1（1）f1（2）f329歐拉公式(續(xù))歐拉公式的推廣

設(shè)G是有k(k

2)個連通分支的平面圖,則

p

q+f=k+1證明：設(shè)第i個連通分支有pi個頂點(diǎn),qi

條邊和fi

個面.對各連通分支用歐拉公式,

pi

qi+fi=2,i=1,2,…,k求和并注意f=f1+…+fp-(k

1),即得

p

q+f+(k

1)=2kp

q+f=k+130f0f3fgf2f1acdebp

q+f=k+1p=6，

q=7，

f=431定理

(歐拉公式)設(shè)G為p階q條邊f(xié)個面的連通平面圖，則

p

q+f=2.握手定理定理只存在以下幾種正多面體：正四面體、正六面體、正八面體、正十二面體、正二十面體32凸多面體

平面圖的理論與多面體的研究密切相關(guān):事實(shí)上,由于每個凸多面體P可以與一個連通可平面圖G對應(yīng),G的頂點(diǎn)和邊是P的頂點(diǎn)和棱,那么G的每個頂點(diǎn)的度至少為3.由于G是一個平面圖,則P的面就是G的面,并且G的每一條邊落在兩個不同面的邊界上.

一個多面體P的頂點(diǎn),棱和面的數(shù)目分別用V,E和F來表示,而且,這些分別是連通圖G的頂點(diǎn),邊和面的數(shù)目.故歐拉公式可寫成V-E+F=2,這就是著名的Euler凸多面體公式.

33定理只存在以下幾種正多面體：正四面體、正六面體、正八面體、正十二面體、正二十面體證明：設(shè)正多面體的每個頂點(diǎn)的度數(shù)為m,每個面的次數(shù)為c,34正六面體正四面體正十二面體35無解正八面體正二十面體36與歐拉公式有關(guān)的定理

定理設(shè)G為p階連通平面圖,有q條邊,且每個面的次數(shù)不小于l(l

3),則

證明：由于在計算面數(shù)之和時，每個邊被計算了兩次，因此各面次數(shù)之和等于邊數(shù)的2倍，再由歐拉公式得：2q

lf=l(2+q-p)

37推論

K5和K3,3不是平面圖.證明：用反證法,假設(shè)它們是平面圖,則

K5:p=5,q=10,l=3

K3,3:p=6,q=9,l=4與定理矛盾.K5K3,3K5和K3,3稱為基本的不可平面圖，或Kuratowski

圖。38與歐拉公式有關(guān)的定理(續(xù))定理:設(shè)G為有k(k

2)個連通分支的平面圖,且每個面的次數(shù)不小于l(l

3),則39

定理9

設(shè)G是簡單平面圖，有p(p≥3)個頂點(diǎn)，q條邊，則q≤3p-6

證明:設(shè)G有k(k≥1)個連通分支。若G為樹或森林，根據(jù)定理，

q=p-k≤p=p+6-6=p+3+3-6≤p+p+p-6=3p–6。若G不是樹，也不是森林，則G中必含有圈。又因?yàn)镚是簡單平面圖，所以其中的圈的長度均大于等于3，因而各面次數(shù)l≥3，又當(dāng)l=3時，達(dá)到最大值3，由定理有：40定理9設(shè)G是極大平面圖，有p(p≥3)個頂點(diǎn)，q條邊，則q=3p–6,f=2p-4

證明：設(shè)G有f個面。由于極大平面圖是連通圖，所以G是連通圖。由歐拉公式得f=2+q-p，又因?yàn)镚是極大平面圖，G的每個面的次數(shù)均為3，又因?yàn)閳DG的所有面的次數(shù)之和等于邊數(shù)的2倍,所以2q=3f=3(2+q-p)。整理后，q=3p–6，從而f=2+3p-6-p=2p-4。41定理9

設(shè)G是簡單平面圖，則G的最小度

(G)≤5。證明：設(shè)G有p個頂點(diǎn)，q條邊。當(dāng)p≤6，因?yàn)镚是簡單圖，可知，

(G)≤

(G)≤5。以下證p≥7的情況，若

(G)≥6，即每個頂點(diǎn)的度數(shù)大于等于6，G中所有頂點(diǎn)度數(shù)之和大于等于6p。于是

2q=≥6p，q≥3p＞3p–6，即q＞3p–6，與定理矛盾。42為討論平面圖的判別法,下面給出兩個重要的定義。定義

設(shè)e=(u,v)為圖G的一條邊,在G中刪除e,增加新的頂點(diǎn)w,使u和v均與w相鄰,稱在G中插入2度頂點(diǎn)w。設(shè)w為G中一個2度頂點(diǎn),w與u和v相鄰,刪除w,增加新邊(u,v),稱為在G中消去2度頂點(diǎn)w。43

G1與G2同胚:G1與G2同構(gòu),或經(jīng)過反復(fù)插入、或消去2度頂點(diǎn)后同構(gòu)收縮邊e

如下圖從(1)到(2)下圖中,(a)與K3同胚,(b)與K4同胚。44同胚。e1e2u1u2u3e3u1u3u1u3e3e1e2u1u2u3e3u1u3e345例：同胚圖46定理

G是平面圖

G中不含與K5同胚的子圖,也不含與K3,3同胚的子圖.即：

G是平面圖

G中不包含與K5和K3,3在2度頂點(diǎn)內(nèi)同構(gòu)的子圖。定理9一個圖是平面圖當(dāng)且僅當(dāng)它既沒有收縮到K5的子圖，也沒有收縮到K3,3的子圖。庫拉圖斯基(Kufatowski)定理2庫拉圖斯基(Kufatowski)定理147THEOREMAgraphisnonplanarifandonlyifitcontainsasubgraph

homeomorphictoK3,3orK5.Kuratowski

定理的實(shí)際應(yīng)用較為困難。庫拉圖斯基給出了平面圖的充要條件,但用它并不能判別一個圖是否是平面圖的有效算法.48例1證明彼得松圖不是平面圖。證法1:將彼得松圖頂點(diǎn)標(biāo)順序如右圖(1)所示。在圖中將邊(a,f),(b,g),(c,h),(d,i),(e,j)收縮后,得到右圖(2)。它是K5