復(fù)試2離散結(jié)構(gòu)

8.4

平面圖–平面圖與平面嵌入–平面圖的面及其次數(shù)–極大平面圖–極小非平面圖–歐拉公式–庫(kù)拉圖斯基定理–平面圖的對(duì)偶圖1平面圖與非平面圖定義8.6如果能將圖G除頂點(diǎn)外邊不相交地畫在平面上,則稱G是平面圖.這個(gè)畫出的無(wú)邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.例如下圖中(1)~(4)是平面圖,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面圖.23平面圖的面與次數(shù)設(shè)G是一個(gè)平面嵌入G的面:由G的邊將平面劃分成的每一個(gè)區(qū)域無(wú)限面(外部面):面積無(wú)限的面,用R0表示有限面(內(nèi)部面):面積有限的面,用R1,R2,…,Rk表示面Ri的邊界:包圍Ri的所有邊構(gòu)成的回路組面Ri的次數(shù):Ri邊界的長(zhǎng)度，用deg(Ri)表示說明:構(gòu)成一個(gè)面的邊界的回路組可能是初級(jí)回路,簡(jiǎn)單回路,也可能是復(fù)雜回路,甚至還可能是非連通的回路之并.實(shí)例例1

右圖有4

個(gè)面R1的邊界:R2的邊界:R3的邊界:R0的邊界:abcefgabcdde,

fgdeg(R1)=1deg(R2)=3deg(R3)=2deg(R0)=84實(shí)例例2右邊2個(gè)圖是同一平面圖的平面嵌入.R1在(1)中是外部面,在(2)中是內(nèi)部面;R2在(1)中是內(nèi)部面,

在(2)中是外部面.說明:(1)一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入,它們都同構(gòu).(2)可以通過變換(測(cè)地投影法)把平面圖的任何一面作為外部面R2(1)R1R3(2)5R2

R1R36平面圖的面與次數(shù)(續(xù))定理8.9

平面圖各面的次數(shù)之和等于邊數(shù)的2倍證一條邊或者是2個(gè)面的公共邊界,或者在一個(gè)面的邊界中出現(xiàn)2次.在計(jì)算各面的次數(shù)之和時(shí),每條邊恰好被計(jì)算

2次.極大平面圖定義8.8若G是簡(jiǎn)單平面圖,且在任意兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖,則稱G為極大平面圖例如K1,K2,K3,K4都是極大平面圖(1)是K5刪去一條邊,

是極大平面圖.

(2)、(3)不是.(1)7(2)(3)極大平面圖的性質(zhì)極大平面圖是連通的

設(shè)G為n(n?3)階簡(jiǎn)單圖,G為極大平面圖的充分必要條件是,G每個(gè)面的次數(shù)均為3.例如極大平面圖8外部面的次數(shù)為4非極大平面圖極小非平面圖定義8.8若G是非平面圖,并且任意刪除一條邊所得圖都是平面圖,則稱G為極小非平面圖例如K5,K3,3都是極小非平面圖下述4個(gè)圖也都是極小非平面圖910歐拉公式定理8.10

設(shè)G為n階m條邊r個(gè)面的連通平面圖,則n-m+r=2證

對(duì)邊數(shù)m做歸納證明.

m=0,

G為平凡圖,結(jié)論成立.設(shè)m=k(k?0)時(shí)結(jié)論成立,

對(duì)m=k+1,若G中無(wú)圈,則G必有一個(gè)度數(shù)為1的頂點(diǎn)v,刪除v及關(guān)聯(lián)的邊,記作G￠.

G￠連通,有n-1個(gè)頂點(diǎn),k條邊和r個(gè)面.由歸納假設(shè),

(n-1)-k+r=2,

即n-(k+1)+r=2,

得證m=k+1時(shí)結(jié)論成立.否則,刪除一個(gè)圈上的一條邊,記作G￠.

G￠連通,有n個(gè)頂點(diǎn),k條邊和r-1個(gè)面.由歸納假設(shè),n-k+(r-1)=2,即n-(k+1)+r=2.得證m=k+1時(shí)結(jié)論也成立.

證畢.11歐拉公式(續(xù))推論設(shè)平面圖G有p

(p?2)個(gè)連通分支,則n

-

m

+

r

=

p

+

1其中n,m,r

分別是G的階數(shù),邊數(shù)和面數(shù).證設(shè)第i

個(gè)連通分支有ni個(gè)頂點(diǎn),mi條邊和ri個(gè)面.對(duì)各連通分支用歐拉公式,ni

-

mi

+

ri

=2,

i

=

1,

2,

…

,

p求和并注意r

=r1+…+rp

-p+1,即得n

-

m

+

r

=

p

+

1歐拉公式(續(xù))定理8.11設(shè)G為n階連通平面圖,有m條邊,且每個(gè)面的次數(shù)不小于l

(l

?3),

則證由各面次數(shù)之和等于邊數(shù)的2倍及歐拉公式得2m

?

lr

=

l

(2+m-

n)可解得所需結(jié)論.(n

-

2)12l

-

2m

￡l實(shí)例例3證明K5和K3,3不是平面圖證K5

:n=5,

m=10,

l=3K3,3

:

n=6,

m=9,

l=4不滿足定理8.11的條件例4

設(shè)簡(jiǎn)單連通平面圖有n(n?3)個(gè)頂點(diǎn)、m條邊,則m￡3n-6證不難證明3階以上的簡(jiǎn)單連通平面圖每個(gè)面的次數(shù)至少為3,

由定理8.11立即得到要證的結(jié)論.13同胚與收縮消去2度頂點(diǎn)v如圖從(1)到(2)插入2度頂點(diǎn)v

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

如圖從(3)到(4)(3)14(4)15庫(kù)拉圖斯基(Kuratowski)定理定理8.13

一個(gè)圖是平面圖當(dāng)且僅當(dāng)它既不含與K5同胚的子圖,

也不含與K3,3同胚的子圖.定理8.14

一個(gè)圖是平面圖當(dāng)且僅當(dāng)它既無(wú)可收縮為K5的子圖,

也無(wú)可收縮為K3,3的子圖.實(shí)例也與K3,3同胚可收縮到K3,3例5

證明下面2個(gè)圖均為非平面圖.與K5同胚也可收縮到K51617對(duì)偶圖定義8.11設(shè)平面圖G有n個(gè)頂點(diǎn),m條邊和r個(gè)面,G的對(duì)偶圖G*=<V*,E*>構(gòu)造如下:在G的每一個(gè)面Ri中任取一個(gè)點(diǎn)vi*作為G*的頂點(diǎn),V*=

{

vi*|

i=1,2,…,r

}.對(duì)G每一條邊ek,若ek在G的面Ri與Rj的公共邊界上,則作邊

ek*=(vi*,vj*),

且與ek相交;若ek只在面Ri的邊界上,則作環(huán)

ek*=(vi*,vi*).

E*={

ek*|

k=1,2,…,m

}.實(shí)例性質(zhì)G*是平面圖，而且是平面嵌入.G*是連通的.若e為G中的環(huán),則G*中e*為橋;若e為橋,則G*中e*為環(huán).同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu).如(1)和(3)(1)(2)(3)1819對(duì)偶圖(續(xù))定理8.15

設(shè)G*是連通平面圖G的對(duì)偶圖,n*,

m*,

r*和n,m,r分別為G*和G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，則n*=

rm*=mr*=n設(shè)G*