離散數(shù)學(xué)--65平面圖ppt課件

1、6.4.4 平面圖平面圖 平面圖與平面嵌入平面圖與平面嵌入平面圖的面及其次數(shù)平面圖的面及其次數(shù)極大平面圖極大平面圖極小非平面圖極小非平面圖歐拉公式歐拉公式庫拉圖斯基定理庫拉圖斯基定理平面圖的對(duì)偶圖平面圖的對(duì)偶圖平面圖與非平面圖平面圖與非平面圖定義定義6.22 如果能將圖如果能將圖G除頂點(diǎn)外邊不相交地畫在平面上除頂點(diǎn)外邊不相交地畫在平面上, 則稱則稱G是平面圖是平面圖. 這個(gè)畫出的無邊相交的圖稱作這個(gè)畫出的無邊相交的圖稱作G的平面的平面嵌入嵌入. 沒有平面嵌入的圖稱作非平面圖沒有平面嵌入的圖稱作非平面圖.例如例如 下圖中下圖中(1)(4)是平面圖是平面圖, (2)是是(1)的平面嵌入，的平面嵌入

2、， (4)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.平面圖的面與次數(shù)平面圖的面與次數(shù)設(shè)設(shè)G是一個(gè)平面嵌入是一個(gè)平面嵌入G的面的面: 由由G的邊將平面劃分成的每一個(gè)區(qū)域的邊將平面劃分成的每一個(gè)區(qū)域無限面無限面(外部面外部面): 面積無限的面面積無限的面, 用用R0表示表示有限面有限面(內(nèi)部面內(nèi)部面): 面積有限的面面積有限的面, 用用R1, R2, Rk表示表示 面面Ri的邊界的邊界: 包圍包圍Ri的所有邊構(gòu)成的回路組的所有邊構(gòu)成的回路組面面Ri的次數(shù)的次數(shù): Ri邊界的長(zhǎng)度，用邊界的長(zhǎng)度，用deg(Ri)表示表示 說明說明: 構(gòu)成一個(gè)面的邊界的回路組可能是初級(jí)回路構(gòu)成一個(gè)面

3、的邊界的回路組可能是初級(jí)回路, 簡(jiǎn)單回簡(jiǎn)單回路路, 也可能是復(fù)雜回路也可能是復(fù)雜回路, 甚至還可能是非連通的回路之并甚至還可能是非連通的回路之并.實(shí)例實(shí)例例例1 右圖有右圖有 個(gè)面?zhèn)€面4deg(R1)=deg(R2)=deg(R3)=deg(R0)=1328R1的邊界的邊界:R2的邊界的邊界:R3的邊界的邊界:R0的邊界的邊界:abcefgabcdde, fg實(shí)例實(shí)例例例2 右邊右邊2個(gè)圖是同一個(gè)圖是同一平面圖的平面嵌入平面圖的平面嵌入. R1在在(1)中是外部面中是外部面, 在在(2)中是內(nèi)部面中是內(nèi)部面; R2在在(1)中是內(nèi)部面中是內(nèi)部面, 在在(2)中是外部面中是外部面. (1)R1R

4、2R3(2)R1R2R3說明說明: (1) 一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入一個(gè)平面圖可以有多個(gè)不同形式的平面嵌入, 它們都同構(gòu)它們都同構(gòu).(2) 可以通過變換可以通過變換(測(cè)地投影法測(cè)地投影法)把平面圖的任何一面作為把平面圖的任何一面作為外部面外部面平面圖的面與次數(shù)平面圖的面與次數(shù)( (續(xù)續(xù)) )定理定理6.13 平面圖各面的次數(shù)之和等于邊數(shù)的平面圖各面的次數(shù)之和等于邊數(shù)的2倍倍證證 一條邊或者是一條邊或者是2個(gè)面的公共邊界個(gè)面的公共邊界, 或者在一個(gè)面的邊界或者在一個(gè)面的邊界中出現(xiàn)中出現(xiàn)2次次. 在計(jì)算各面的次數(shù)之和時(shí)在計(jì)算各面的次數(shù)之和時(shí), 每條邊恰好被計(jì)算每條邊恰好被計(jì)算2次次.

5、極大平面圖極大平面圖定義定義6.24 若若G是簡(jiǎn)單平面圖是簡(jiǎn)單平面圖, 且在任意兩個(gè)不相鄰的頂點(diǎn)且在任意兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖之間加一條新邊所得圖為非平面圖, 則稱則稱G為極大平面圖為極大平面圖例如例如 K1, K2, K3, K4都是極大平面圖都是極大平面圖(1)是是K5刪去一條邊刪去一條邊, 是極大平面圖是極大平面圖. (2)、(3)不是不是.(2)(3)(1)極大平面圖的性質(zhì)極大平面圖的性質(zhì)極大平面圖是連通的極大平面圖是連通的 設(shè)設(shè)G為為n(n3)階簡(jiǎn)單圖階簡(jiǎn)單圖, G為極大平面圖的充分必要條為極大平面圖的充分必要條 件是件是, G每個(gè)面的次數(shù)均為每個(gè)面的次數(shù)均為

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

7、設(shè)m=k(k0)時(shí)結(jié)論成立時(shí)結(jié)論成立, 對(duì)對(duì)m=k+1,若若G中無圈中無圈, 則則G必有一個(gè)度數(shù)為必有一個(gè)度數(shù)為1的頂點(diǎn)的頂點(diǎn)v, 刪除刪除v及關(guān)聯(lián)的及關(guān)聯(lián)的邊邊, 記作記作G. G連通連通, 有有n-1個(gè)頂點(diǎn)個(gè)頂點(diǎn), k條邊和條邊和r個(gè)面?zhèn)€面. 由歸納由歸納假假設(shè)設(shè), (n-1)-k+r=2, 即即n-(k+1)+r=2, 得證得證m=k+1時(shí)結(jié)論成立時(shí)結(jié)論成立. 否則否則, 刪除一個(gè)圈上的一條邊刪除一個(gè)圈上的一條邊,記作記作G. G連通連通, 有有n個(gè)頂個(gè)頂點(diǎn)點(diǎn),k條邊和條邊和r-1個(gè)面?zhèn)€面. 由歸納假設(shè)由歸納假設(shè), n-k+(r-1)=2, 即即n-(k+1)+r=2. 得得證證m=k+

8、1時(shí)結(jié)論也成立時(shí)結(jié)論也成立. 證畢證畢.歐拉公式歐拉公式(續(xù)續(xù))推論推論 設(shè)平面圖設(shè)平面圖G有有 p (p2) 個(gè)連通分支個(gè)連通分支, 那么那么 n m + r = p + 1其中其中n, m, r 分別是分別是G的階數(shù)的階數(shù), 邊數(shù)和面數(shù)邊數(shù)和面數(shù).證證 設(shè)第設(shè)第 i 個(gè)連通分支有個(gè)連通分支有 ni個(gè)頂點(diǎn)個(gè)頂點(diǎn), mi 條邊和條邊和 ri 個(gè)面?zhèn)€面. 對(duì)對(duì)各各連通分支用歐拉公式連通分支用歐拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r = r1+rp p+1, 即得即得 n m + r = p + 1歐拉公式歐拉公式(續(xù)續(xù))定理定理6.15 設(shè)設(shè)

9、G為為n階連通平面圖階連通平面圖, 有有m條邊條邊, 且每個(gè)面的次且每個(gè)面的次數(shù)不小于數(shù)不小于l (l 3), 那么那么 證證 由各面次數(shù)之和等于邊數(shù)的由各面次數(shù)之和等于邊數(shù)的2倍及歐拉公式得倍及歐拉公式得 2m lr = l (2+m-n)可解得所需結(jié)論可解得所需結(jié)論.)2(2nllm實(shí)例實(shí)例例例4 設(shè)簡(jiǎn)單連通平面圖有設(shè)簡(jiǎn)單連通平面圖有n(n3)個(gè)頂點(diǎn)、個(gè)頂點(diǎn)、m條邊條邊, 那么那么 m3n-6例例3 證明證明 K5 和和 K3,3不是平面圖不是平面圖證證 不難證明不難證明3階以上的簡(jiǎn)單連通平面圖每個(gè)面的次數(shù)至階以上的簡(jiǎn)單連通平面圖每個(gè)面的次數(shù)至少為少為3, 由定理由定理6.15立即得到要證

10、的結(jié)論立即得到要證的結(jié)論.證證 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4不滿足定理不滿足定理6.15的條件的條件同胚與收縮同胚與收縮消去消去2度頂點(diǎn)度頂點(diǎn)v 如圖從如圖從(1)到到(2)插入插入2度頂點(diǎn)度頂點(diǎn)v 如圖從如圖從(2)到到(1)G1與與G2同胚同胚: G1與與G2同構(gòu)同構(gòu), 或或經(jīng)過反復(fù)插入、或消去經(jīng)過反復(fù)插入、或消去2度頂度頂點(diǎn)后同構(gòu)點(diǎn)后同構(gòu)收縮邊收縮邊e 如圖從如圖從(3)到到(4)(3)(4)庫拉圖斯基庫拉圖斯基(Kuratowski)(Kuratowski)定理定理定理定理6.16 一個(gè)圖是平面圖當(dāng)且僅當(dāng)它既不含與一個(gè)圖是平面圖當(dāng)且僅

11、當(dāng)它既不含與K5同胚的同胚的子圖子圖, 也不含與也不含與K3,3同胚的子圖同胚的子圖.定理定理6.17 一個(gè)圖是平面圖當(dāng)且僅當(dāng)它既無可收縮為一個(gè)圖是平面圖當(dāng)且僅當(dāng)它既無可收縮為K5的的子圖子圖, 也無可收縮為也無可收縮為K3,3的子圖的子圖. 實(shí)例實(shí)例與與K3,3同胚同胚也可收縮到也可收縮到K3,3例例5 證明下面證明下面2個(gè)圖均為非平面圖個(gè)圖均為非平面圖. 與與K5同胚同胚也可收縮到也可收縮到K5對(duì)偶圖對(duì)偶圖定義定義6.28 設(shè)平面圖設(shè)平面圖G有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn), m條邊和條邊和r個(gè)面?zhèn)€面, G的對(duì)偶的對(duì)偶圖圖G*=構(gòu)造如下構(gòu)造如下: 在在G的每一個(gè)面的每一個(gè)面Ri中任取一個(gè)點(diǎn)中任取一個(gè)點(diǎn)v

12、i*作為作為G*的頂點(diǎn)的頂點(diǎn), V*= vi*| i=1,2,r . 對(duì)對(duì)G每一條邊每一條邊ek, 若若ek在在G的面的面Ri與與Rj的公共邊界上的公共邊界上, 則作則作邊邊ek*=(vi*,vj*), 且與且與ek相交相交; 若若ek只在面只在面Ri的邊界上的邊界上, 則作環(huán)則作環(huán)ek*=(vi*,vi*). E*= ek*| k=1,2, ,m .實(shí)例實(shí)例性質(zhì)性質(zhì)G*是平面圖，而且是平面嵌入是平面圖，而且是平面嵌入.G*是連通的是連通的.若若e為為G中的環(huán)中的環(huán), 則則G*中中e*為橋?yàn)闃? 若若e為橋?yàn)闃? 則則G*中中e*為環(huán)為環(huán).同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu)同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu). 如如(1)和和(3)(1)(2)(3)對(duì)偶圖對(duì)偶圖(續(xù)續(xù))定理定理6.18 設(shè)設(shè)G*是連通平面圖是連通平面圖G的對(duì)偶圖的對(duì)偶圖, n*, m*, r*和和n, m, r分別為分別為G*和和G的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)，那么的頂點(diǎn)數(shù)、