離散完整PPT課件

1、18.4 平面圖平面圖 平面圖與平面嵌入平面圖與平面嵌入平面圖的面、有限面、無限面平面圖的面、有限面、無限面面的次數(shù)面的次數(shù)極大平面圖極大平面圖極小非平面圖極小非平面圖歐拉公式歐拉公式平面圖的對偶圖平面圖的對偶圖 2平面圖和平面嵌入平面圖和平面嵌入 定義定義 如果能將圖如果能將圖g除頂點外邊不相交地畫在平面上除頂點外邊不相交地畫在平面上, 則稱則稱g是是平面圖平面圖. 這個畫出的無邊相交的圖稱作這個畫出的無邊相交的圖稱作g的的平面嵌入平面嵌入. 沒有平面嵌入的圖稱作沒有平面嵌入的圖稱作非平面圖非平面圖. 例如例如 下圖中下圖中(1)(4)是平面圖是平面圖, (2)是是(1)的平面嵌入，的平面嵌

2、入，(4)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.3平面圖和平面嵌入平面圖和平面嵌入( (續(xù)續(xù)) )今后稱一個圖是平面圖今后稱一個圖是平面圖, 可以是指定義中的平面圖可以是指定義中的平面圖, 又可以又可以是指平面嵌入是指平面嵌入, 視當(dāng)時的情況而定視當(dāng)時的情況而定. 當(dāng)討論的問題與圖的畫當(dāng)討論的問題與圖的畫法有關(guān)時法有關(guān)時, 是指平面嵌入是指平面嵌入. k5和和k3,3是非平面圖是非平面圖設(shè)設(shè)g g, 若若g為平面圖為平面圖, 則則g 也是也是 平面圖平面圖; 若若g 為非平面圖為非平面圖, 則則g也也 是非平面圖是非平面圖. kn(n 5), k3,n(n 3)都是非平

3、面圖都是非平面圖. 平行邊與環(huán)不影響圖的平面性平行邊與環(huán)不影響圖的平面性. k5k3,34平面圖的面與次數(shù)平面圖的面與次數(shù)設(shè)設(shè)g是一個平面嵌入是一個平面嵌入g的面的面: 由由g的邊將平面劃分成的每一個區(qū)域的邊將平面劃分成的每一個區(qū)域無限面無限面(外部面外部面): 面積無限的面面積無限的面, 用用r0表示表示有限面有限面(內(nèi)部面內(nèi)部面): 面積有限的面面積有限的面, 用用r1, r2, rk表示表示 面面ri的邊界的邊界: 包圍包圍ri的所有邊構(gòu)成的回路組的所有邊構(gòu)成的回路組面面ri的次數(shù)的次數(shù): ri邊界的長度，用邊界的長度，用deg(ri)表示表示 說明說明: 構(gòu)成一個面的邊界的回路組可能是

4、初級回路構(gòu)成一個面的邊界的回路組可能是初級回路, 簡單回簡單回路路, 也可能是復(fù)雜回路也可能是復(fù)雜回路, 還可能是非連通的回路之并還可能是非連通的回路之并. 定理定理 平面圖各面的次數(shù)之和等于邊數(shù)的平面圖各面的次數(shù)之和等于邊數(shù)的2倍倍.5平面圖的面與次數(shù)平面圖的面與次數(shù)( (續(xù)續(xù)) )例例1 右圖有右圖有4個面?zhèn)€面, deg(r1)=1, deg(r2)=3, deg(r3)=2, deg(r0)=8. 請寫各面的邊界請寫各面的邊界.例例2 左邊左邊2個圖是同一個平面?zhèn)€圖是同一個平面圖的平面嵌入圖的平面嵌入. r1在在(1)中是中是外部面外部面, 在在(2)中是內(nèi)部面中是內(nèi)部面; r2在在(1

5、)中是內(nèi)部面中是內(nèi)部面, 在在(2)中是中是外部面外部面. 其實其實, 在平面嵌入中在平面嵌入中可把任何面作為外部面可把任何面作為外部面.6極大平面圖極大平面圖 定義定義 若若g是簡單平面圖是簡單平面圖, 并且在任意兩個不相鄰的頂點之并且在任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖間加一條新邊所得圖為非平面圖, 則稱則稱g為為極大平面圖極大平面圖.性質(zhì)性質(zhì)若簡單平面圖中已無不相鄰頂點，則是極大平面圖若簡單平面圖中已無不相鄰頂點，則是極大平面圖. 如如 k1, k2, k3, k4都是極大平面圖都是極大平面圖. 極大平面圖必連通極大平面圖必連通. 階數(shù)大于等于階數(shù)大于等于3的極大平面圖中

6、不可能有割點和橋的極大平面圖中不可能有割點和橋. 設(shè)設(shè)g為為n(n 3)階極大平面圖階極大平面圖, 則則g每個面的次數(shù)均為每個面的次數(shù)均為3. 任何任何n(n 4)階極大平面圖階極大平面圖g均有均有(g) 3. 7實例實例3個圖都是平面圖個圖都是平面圖, 但只有右邊的圖為極大平面圖但只有右邊的圖為極大平面圖. 8極小非平面圖極小非平面圖 定義定義 若若g是非平面圖是非平面圖, 并且任意刪除一條邊所得圖并且任意刪除一條邊所得圖都是平面圖都是平面圖, 則稱則稱g為為極小非平面圖極小非平面圖.說明說明: k5, k3,3都是極小非平面圖都是極小非平面圖 極小非平面圖必為簡單圖極小非平面圖必為簡單圖下

7、面下面4個圖都是極小非平面圖個圖都是極小非平面圖 9歐拉公式歐拉公式 定理定理8.11 (歐拉公式歐拉公式) 設(shè)設(shè)g為為n階階m條邊條邊r個面的連通平面圖，個面的連通平面圖，則則 n m+r=2. 證證 對邊數(shù)對邊數(shù)m做歸納證明做歸納證明. m=0, g為平凡圖為平凡圖, 結(jié)論為真結(jié)論為真.設(shè)設(shè)m=k(k 0)結(jié)論為真結(jié)論為真, m=k+1時分情況討論如下時分情況討論如下: (1) g中無圈中無圈, 則則g必有一個度數(shù)為必有一個度數(shù)為1的頂點的頂點v, 刪除刪除v及它關(guān)及它關(guān)聯(lián)的邊聯(lián)的邊, 記作記作g . g 連通連通, 有有n-1個頂點個頂點, k條邊和條邊和r個面?zhèn)€面. 由由歸歸納假設(shè)納假

8、設(shè), (n-1)-k+r=2, 即即n-(k+1)+r=2, 得證得證m=k+1時結(jié)論成立時結(jié)論成立. (2) 否則否則,刪除一個圈上的一條邊刪除一個圈上的一條邊,記作記作g . g 連通連通, 有有n個頂個頂點點,k條邊和條邊和r-1個面?zhèn)€面. 由由歸納假設(shè)歸納假設(shè), n-k+(r-1)=2, 即即n-(k+1)+r=2,得證得證m=k+1時結(jié)論也成立時結(jié)論也成立. 證畢證畢. 10歐拉公式歐拉公式( (續(xù)續(xù)) )歐拉公式的推廣歐拉公式的推廣 設(shè)設(shè)g是有是有 p (p 2) 個連通分支的平面圖個連通分支的平面圖, 則則 n m + r = p + 1證證 設(shè)第設(shè)第 i 個連通分支有個連通分支

9、有 ni個頂點個頂點, mi 條邊和條邊和 ri 個面?zhèn)€面. 對各連通分支用歐拉公式對各連通分支用歐拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r = r1+rp+ p 1, 即得即得 n m + r = p + 111與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理 )2(2 nllmk5k3,3定理定理 設(shè)設(shè)g為為n階連通平面圖階連通平面圖, 有有m條邊條邊, 且每個面的次數(shù)不且每個面的次數(shù)不小于小于l (l 3), 則則 證證 由定理由定理 (各面次數(shù)之和等于邊數(shù)的各面次數(shù)之和等于邊數(shù)的2倍倍)及歐拉公式得及歐拉公式得 2m lr = l (2+m-

10、n)可解得所需結(jié)論可解得所需結(jié)論. 推論推論 k5 和和 k3,3不是平面圖不是平面圖.證證 用反證法用反證法, 假設(shè)它們是平面圖假設(shè)它們是平面圖,則則 k5 : n=5, m=10, l=3 k3,3 : n=6, m=9, l=4與定理矛盾與定理矛盾.12與歐拉公式有關(guān)的定理與歐拉公式有關(guān)的定理( (續(xù)續(xù)) )1(2 pnllm定理定理: 設(shè)設(shè)g為有為有 p (p 2) 個連通分支的平面圖個連通分支的平面圖, 且每個面的次數(shù)不小于且每個面的次數(shù)不小于l (l 3), 則則定理定理 設(shè)設(shè)g為簡單平面圖，則為簡單平面圖，則 (g) 5.13同胚與收縮同胚與收縮 消去消去2度頂點度頂點v 如上圖

11、從如上圖從(1)到到(2)插入插入2度頂點度頂點v 如上圖從如上圖從(2)到到(1)g1與與g2同胚同胚: g1與與g2同構(gòu)同構(gòu), 或或經(jīng)過反復(fù)插入、或消去經(jīng)過反復(fù)插入、或消去2度頂度頂點后同構(gòu)點后同構(gòu)收縮邊收縮邊e 如下圖從如下圖從(1)到到(2)14庫拉圖斯基定理庫拉圖斯基定理定理定理 g是平面圖是平面圖g中不含與中不含與k5同胚的子圖同胚的子圖, 也不也不含與含與k3,3同胚的子圖同胚的子圖.定理定理 g是平面圖是平面圖g中無可收縮為中無可收縮為k5的子圖的子圖, 也無也無可收縮為可收縮為k3,3的子圖的子圖. 15非平面圖證明非平面圖證明例例 證明下述證明下述2個圖均為非平面圖個圖均為

12、非平面圖. 證證圖中紅色部分分別與圖中紅色部分分別與k3,3和和 k5 同胚同胚16平面圖的對偶圖平面圖的對偶圖 定義定義 設(shè)平面圖設(shè)平面圖g, 有有n個頂點個頂點, m條邊和條邊和r個面?zhèn)€面, 構(gòu)造構(gòu)造g的的對偶圖對偶圖g*=如下：如下：在在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)則作環(huán)ek

13、*=(vi*,vi*). e*= ek*| k=1,2, ,m . 17平面圖的對偶圖（續(xù)）平面圖的對偶圖（續(xù)）例例 黑色實線為原平面圖黑色實線為原平面圖, 紅色虛線為其對偶圖紅色虛線為其對偶圖 18平面圖的對偶圖平面圖的對偶圖( (續(xù)續(xù)) )性質(zhì)：性質(zhì)：g*是平面圖，而且是平面嵌入是平面圖，而且是平面嵌入.g*是連通圖是連通圖若邊若邊e為為g中的環(huán)，則中的環(huán)，則g*與與e對應(yīng)的邊對應(yīng)的邊e*為橋為橋; 若若e為橋，則為橋，則g*中與中與e對應(yīng)的邊對應(yīng)的邊e*為環(huán)為環(huán).在多數(shù)情況下，在多數(shù)情況下，g*含有平行邊含有平行邊.同構(gòu)的平面圖的對偶圖不一定同構(gòu)同構(gòu)的平面圖的對偶圖不一定同構(gòu). 上面兩個平面圖是同構(gòu)的上面兩個平面圖是同構(gòu)的, 但它們的對偶圖不同構(gòu)但它們的對偶圖不同構(gòu). 19平面圖與對偶圖的階數(shù)、邊數(shù)與面數(shù)之間的關(guān)系平面圖與對偶圖的階數(shù)、