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

8.4

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

右圖有4

個面R1的邊界:R2的邊界:R3的邊界:R0的邊界:abcefgabcdde,

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

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

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

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

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

是極大平面圖.

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

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

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

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

m=0,

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

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

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

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

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

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

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

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

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

-

m

+

r

=

p

+

1其中n,m,r

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

個連通分支有ni個頂點,mi條邊和ri個面.對各連通分支用歐拉公式,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條邊,且每個面的次數(shù)不小于l

(l

?3),

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

?

lr

=

l

(2+m-

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

-

2)12l

-

2m

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

:n=5,

m=10,

l=3K3,3

:

n=6,

m=9,

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

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

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

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

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

一個圖是平面圖當且僅當它既不含與K5同胚的子圖,

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

一個圖是平面圖當且僅當它既無可收縮為K5的子圖,

也無可收縮為K3,3的子圖.實例也與K3,3同胚可收縮到K3,3例5

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

{

vi*|

i=1,2,…,r

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

ek*=(vi*,vj*),

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

ek*=(vi*,vi*).

E*={

ek*|

k=1,2,…,m

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

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

m*,

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

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