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

1平面圖和平面嵌入定義如果能將圖G除頂點外邊不相交地畫在平面上,則稱G是平面圖.這個畫出的無邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.

例如下圖中(1)~(4)是平面圖,(2)是(1)的平面嵌入，(4)是(3)的平面嵌入.(5)是非平面圖.2平面圖和平面嵌入(續(xù))今后稱一個圖是平面圖,可以是指定義中的平面圖,又可以是指平面嵌入,視當時的情況而定.當討論的問題與圖的畫法有關時,是指平面嵌入.K5和K3,3是非平面圖設G

G,若G為平面圖,則G

也是平面圖;若G

為非平面圖,則G也是非平面圖.Kn(n5),K3,n(n3)都是非平面圖.平行邊與環(huán)不影響圖的平面性.K5K3,33平面圖的面與次數(shù)(續(xù))例1右圖有4個面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8.請寫各面的邊界.例2左邊2個圖是同一個平面圖的平面嵌入.R1在(1)中是外部面,在(2)中是內部面;R2在(1)中是內部面,在(2)中是外部面.其實,在平面嵌入中可把任何面作為外部面.5極大平面圖定義若G是簡單平面圖,并且在任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖,則稱G為極大平面圖.性質若簡單平面圖中已無不相鄰頂點，則是極大平面圖.如K1,K2,K3,K4都是極大平面圖.極大平面圖必連通.階數(shù)大于等于3的極大平面圖中不可能有割點和橋.設G為n(n3)階極大平面圖,則G每個面的次數(shù)均為3.任何n(n

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

3.6實例3個圖都是平面圖,但只有右邊的圖為極大平面圖.7極小非平面圖

定義若G是非平面圖,并且任意刪除一條邊所得圖都是平面圖,則稱G為極小非平面圖.說明:K5,K3,3都是極小非平面圖極小非平面圖必為簡單圖下面4個圖都是極小非平面圖8歐拉公式定理8.11(歐拉公式)設G為n階m條邊r個面的連通平面圖，則n

m+r=2.證對邊數(shù)m做歸納證明.m=0,G為平凡圖,結論為真.設m=k(k0)結論為真,m=k+1時分情況討論如下:(1)G中無圈,則G必有一個度數(shù)為1的頂點v,刪除v及它關聯(lián)的邊,記作G

.G

連通,有n-1個頂點,k條邊和r個面.由歸納假設,(n-1)-k+r=2,即n-(k+1)+r=2,得證m=k+1時結論成立.(2)否則,刪除一個圈上的一條邊,記作G

.G

連通,有n個頂點,k條邊和r-1個面.由歸納假設,n-k+(r-1)=2,即n-(k+1)+r=2,得證m=k+1時結論也成立.證畢.9歐拉公式(續(xù))歐拉公式的推廣

設G是有p(p

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

n

m+r=p+1證設第i個連通分支有ni個頂點,mi條邊和ri個面.對各連通分支用歐拉公式,

ni

mi+ri=2,i=1,2,…,p求和并注意r=r1+…+rp+p

1,即得n

m+r=p+110與歐拉公式有關的定理

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

3),則

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

lr=l(2+m-n)可解得所需結論.推論

K5和K3,3不是平面圖.證用反證法,假設它們是平面圖,則K5:n=5,m=10,l=3

K3,3:n=6,m=9,l=4與定理矛盾.11與歐拉公式有關的定理(續(xù))定理:設G為有p(p

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

3),則定理設G為簡單平面圖，則

(G)

5.12同胚與收縮

消去2度頂點v

如上圖從(1)到(2)插入2度頂點v

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

如下圖從(1)到(2)13庫拉圖斯基定理定理

G是平面圖

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

G是平面圖

G中無可收縮為K5的子圖,也無可收縮為K3,3的子圖.14非平面圖證明例證明下述2個圖均為非平面圖.證圖中紅色部分分別與K3,3和K5同胚15平面圖的對偶圖

定義設平面圖G,有n個頂點,m條邊和r個面,構造G的對偶圖G*=<V*,E*>如下：在G的每一個面Ri中任取一個點vi*作為G*的頂點,V*={vi*|i=1,2,…,r}.對G每一條邊ek,若ek在G的面Ri與Rj的公共邊界上,則作邊ek*=(vi*,vj*),且與ek相交;若ek為G中的橋且在面Ri的邊界上,則作環(huán)ek*=(vi*,vi*).

E*={ek*|k=1,2,…,m}.16平面圖的對偶圖（續(xù)）例黑色實線為原平面圖,紅色虛線為其對偶圖

17平面圖的對偶圖(續(xù))性質：G*是平面圖，而且是平面嵌入.G*是連通圖若邊e為G中的環(huán)，則G*與e對應的邊e*為橋;若e為橋，則G*中與e對應的邊e*為環(huán).在多數(shù)情況下，G*含有平行邊.同構的平面圖的對偶圖不一定同構.上面兩個平面圖是同構的,但它們的對偶圖不同構.18平面圖與對偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關系:設G*是平面圖G的對偶圖，n*,m*,r*和n