1、1,6.4.4 平面圖,平面圖與平面嵌入 平面圖的面及其次數(shù) 極大平面圖 極小非平面圖 歐拉公式 庫拉圖斯基定理 平面圖的對偶圖,2,平面圖與非平面圖,定義6.22 如果能將圖G除頂點外邊不相交地畫在平面上, 則稱G是平面圖. 這個畫出的無邊相交的圖稱作G的平面 嵌入. 沒有平面嵌入的圖稱作非平面圖.,例如 下圖中(1)(4)是平面圖, (2)是(1)的平面嵌入， (4)是(3)的平面嵌入. (5)是非平面圖.,3,平面圖的面與次數(shù),設(shè)G是一個平面嵌入 G的面: 由G的邊將平面劃分成的每一個區(qū)域 無限面(外部面): 面積無限的面, 用R0表示 有限面(內(nèi)部面): 面積有限的面, 用R1, R2

2、, Rk表示 面Ri的邊界: 包圍Ri的所有邊構(gòu)成的回路組 面Ri的次數(shù): Ri邊界的長度，用deg(Ri)表示 說明: 構(gòu)成一個面的邊界的回路組可能是初級回路, 簡單回 路, 也可能是復(fù)雜回路, 甚至還可能是非連通的回路之并.,4,實例,例1 右圖有 個面,4,deg(R1)= deg(R2)= deg(R3)= deg(R0)=,1,3,2,8,R1的邊界: R2的邊界: R3的邊界: R0的邊界:,a,bce,fg,abcdde, fg,5,實例,例2 右邊2個圖是同一 平面圖的平面嵌入. R1在(1)中是外部面, 在(2)中是內(nèi)部面; R2在(1)中是內(nèi)部面, 在(2)中是外部面.,說

3、明: (1) 一個平面圖可以有多個不同形式的平面嵌入, 它們都同構(gòu). (2) 可以通過變換(測地投影法)把平面圖的任何一面作為 外部面,6,平面圖的面與次數(shù)(續(xù)),定理6.13 平面圖各面的次數(shù)之和等于邊數(shù)的2倍 證 一條邊或者是2個面的公共邊界, 或者在一個面的邊界 中出現(xiàn)2次. 在計算各面的次數(shù)之和時, 每條邊恰好被計算 2次.,7,極大平面圖,定義6.24 若G是簡單平面圖, 且在任意兩個不相鄰的頂點 之間加一條新邊所得圖為非平面圖, 則稱G為極大平面圖,8,極大平面圖的性質(zhì),極大平面圖是連通的 設(shè)G為n(n3)階簡單圖, G為極大平面圖的充分必要條 件是, G每個面的次數(shù)均為3.,例如

4、,極大平面圖,外部面的次數(shù)為4 非極大平面圖,9,極小非平面圖,定義6.25 若G是非平面圖, 并且任意刪除一條邊所得圖都 是平面圖, 則稱G為極小非平面圖,例如 K5, K3,3都是極小非平面圖 下述4個圖也都是極小非平面圖,10,歐拉公式,定理6.14 設(shè)G為n階m條邊r個面的連通平面圖, 則 nm+r=2 證 對邊數(shù)m做歸納證明. m=0, G為平凡圖, 結(jié)論成立. 設(shè)m=k(k0)時結(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+

5、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 (p2) 個連通分支, 則 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, 即得

6、 n m + r = p + 1,12,歐拉公式(續(xù)),定理6.15 設(shè)G為n階連通平面圖, 有m條邊, 且每個面的次 數(shù)不小于l (l 3), 則 證 由各面次數(shù)之和等于邊數(shù)的2倍及歐拉公式得 2m lr = l (2+m-n) 可解得所需結(jié)論.,13,實例,例4 設(shè)簡單連通平面圖有n(n3)個頂點、m條邊, 則 m3n-6,例3 證明 K5 和 K3,3不是平面圖,證 不難證明3階以上的簡單連通平面圖每個面的次數(shù)至 少為3, 由定理6.15立即得到要證的結(jié)論.,證 K5 : n=5, m=10, l=3,K3,3 : n=6, m=9, l=4 不滿足定理6.15的條件,14,同胚與收縮,

7、消去2度頂點v 如圖從(1)到(2) 插入2度頂點v 如圖從(2)到(1) G1與G2同胚: G1與G2同構(gòu), 或 經(jīng)過反復(fù)插入、或消去2度頂 點后同構(gòu) 收縮邊e 如圖從(3)到(4),15,庫拉圖斯基(Kuratowski)定理,定理6.16 一個圖是平面圖當(dāng)且僅當(dāng)它既不含與K5同胚的 子圖, 也不含與K3,3同胚的子圖. 定理6.17 一個圖是平面圖當(dāng)且僅當(dāng)它既無可收縮為K5的 子圖, 也無可收縮為K3,3的子圖.,16,實例,與K3,3同胚 也可收縮到K3,3,例5 證明下面2個圖均為非平面圖.,與K5同胚 也可收縮到K5,17,對偶圖,定義6.28 設(shè)平面圖G有n個頂點, m條邊和r個

8、面, G的對偶 圖G*=構(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 .,18,實例,性質(zhì) G*是平面圖，而且是平面嵌入. G*是連通的. 若e為G中的環(huán), 則G*中e*為橋; 若e為橋, 則G*中e*為環(huán). 同構(gòu)的平面圖的對偶圖不一定同構(gòu). 如(1)和(3),(1),(2),(3),19,對偶圖(續(xù)),定理6.18 設(shè)G*是連通平面圖G的對偶圖, n*, m*, r*和n, m, r分別為G*和G的頂點數(shù)、邊數(shù)和面數(shù)，則 (1) n*= r (2) m