離散數(shù)學(xué)第三部分圖論6.4

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

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

3、都是非平面圖. 平行邊與環(huán)不影響圖的平面性平行邊與環(huán)不影響圖的平面性. 4平面圖的面與次數(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)表示表示 定理定理 平面圖各面的次數(shù)之和等于邊數(shù)的平面圖各面的次數(shù)之

4、和等于邊數(shù)的2倍倍.證證 每條邊可能在兩個(gè)面的公共邊界上，也可能只在一個(gè)面每條邊可能在兩個(gè)面的公共邊界上，也可能只在一個(gè)面的邊界上的邊界上. 前者前者, 在每個(gè)面的邊界上這條邊只出現(xiàn)一次在每個(gè)面的邊界上這條邊只出現(xiàn)一次, 計(jì)算計(jì)算兩次兩次. 后者后者, 它它在在這個(gè)這個(gè)面的邊界上出現(xiàn)面的邊界上出現(xiàn)2次次, 也也計(jì)算兩次計(jì)算兩次. 5平面圖的面與次數(shù)平面圖的面與次數(shù)( (續(xù)續(xù)) )例例1 右圖有右圖有4個(gè)面?zhèn)€面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 例例2 左邊左邊2個(gè)圖是同一個(gè)平面?zhèn)€圖是同一個(gè)平面圖的平面嵌入圖的平面嵌入. R1在在(1)中是

5、中是外部面外部面, 在在(2)中是內(nèi)部面中是內(nèi)部面; R2在在(1)中是內(nèi)部面中是內(nèi)部面, 在在(2)中是中是外部面外部面. 其實(shí)其實(shí), 在平面嵌入中在平面嵌入中可把任何面作為外部面可把任何面作為外部面.6極大平面圖極大平面圖 定義定義 若若G是簡(jiǎn)單平面圖是簡(jiǎn)單平面圖, 并且在任意兩個(gè)不相鄰的頂點(diǎn)之并且在任意兩個(gè)不相鄰的頂點(diǎn)之間加一條新邊所得圖為非平面圖間加一條新邊所得圖為非平面圖, 則稱則稱G為為極大平面圖極大平面圖.例如例如, K5, K3,3若刪去一條邊是極大平面圖若刪去一條邊是極大平面圖. K1, K2, K3, K4都是極大平面圖都是極大平面圖(它們已無不相鄰頂點(diǎn)它們已無不相鄰頂點(diǎn))

6、.極大平面圖必連通極大平面圖必連通. 階數(shù)大于等于階數(shù)大于等于3的極大平面圖中不可能有割點(diǎn)和橋的極大平面圖中不可能有割點(diǎn)和橋. 任何任何n(n 4)階極大平面圖階極大平面圖G均有均有 (G) 3. 定理定理 n(n 3)階簡(jiǎn)單平面圖是極大平面圖當(dāng)且僅當(dāng)它連通且階簡(jiǎn)單平面圖是極大平面圖當(dāng)且僅當(dāng)它連通且每個(gè)面的次數(shù)都為每個(gè)面的次數(shù)都為3. 7實(shí)例實(shí)例例例 是否是極大平面圖是否是極大平面圖? 不是不是不是不是是是8極小非平面圖極小非平面圖 定義定義 若若G是非平面圖是非平面圖, 并且任意刪除一條邊所得圖并且任意刪除一條邊所得圖都是平面圖都是平面圖, 則稱則稱G為為極小非平面圖極小非平面圖.極小非平面

7、圖必為簡(jiǎn)單圖極小非平面圖必為簡(jiǎn)單圖例如例如, K5, K3,3是極小非平面圖是極小非平面圖9歐拉公式歐拉公式 定理定理 (歐拉公式歐拉公式) 設(shè)設(shè)G為為n階階m條邊條邊r個(gè)面的連通平面圖個(gè)面的連通平面圖, 則則 n m+r=2. 證證 對(duì)邊數(shù)對(duì)邊數(shù)m做歸納證明做歸納證明. m=0, G為平凡圖為平凡圖, 結(jié)論為真結(jié)論為真.設(shè)設(shè)m=k(k 0)結(jié)論為真結(jié)論為真, m=k+1時(shí)分情況討論如下時(shí)分情況討論如下: (1) 若若G中有一個(gè)中有一個(gè)1度頂點(diǎn)度頂點(diǎn)v, 則則G =G-v 連通連通, 有有n-1個(gè)頂點(diǎn)個(gè)頂點(diǎn), k條邊和條邊和r個(gè)面?zhèn)€面. 由由歸納假設(shè)歸納假設(shè), (n-1)-k+r=2, 即即n

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

9、點(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 + 111平面圖的性質(zhì)平面圖的性質(zhì))2(2 nllm定理定理 設(shè)設(shè)G為為n階階m條邊的連通平面圖條邊的連通平面圖, 每個(gè)面的次數(shù)不小于每個(gè)面的次數(shù)不小于l (l 3), 則則 設(shè)設(shè)G為有為有 p (p 2) 個(gè)連通分支的平面圖個(gè)連通分支的平面圖, 且每個(gè)面的次數(shù)不且每個(gè)面的次數(shù)不小于小于l (l 3), 則則證證 由各面次數(shù)之和等于邊數(shù)的由各面次數(shù)之和等

10、于邊數(shù)的2倍及歐拉公式得倍及歐拉公式得 2m lr = l (2+m-n)可解得所需結(jié)論可解得所需結(jié)論. 對(duì)對(duì) p (p 2) 個(gè)連通分支的情況類似可證個(gè)連通分支的情況類似可證.)1(2 pnllm12平面圖的性質(zhì)平面圖的性質(zhì)( (續(xù)續(xù)) )推論推論 K5 和和 K3,3不是平面圖不是平面圖.證證 用反證法用反證法, 假設(shè)它們是平面圖假設(shè)它們是平面圖,則則 K5 : n=5, m=10, l=3 矛盾矛盾. K3,3 : n=6, m=9, l=4 矛盾矛盾. K5K3,39)25(23310 8)26(2449 13同胚與收縮同胚與收縮 消去消去2度頂點(diǎn)度頂點(diǎn)v 如上圖從如上圖從(1)到到(

11、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 如下圖從如下圖從(1)到到(2)14庫拉圖斯基定理庫拉圖斯基定理定理定理 G是平面圖是平面圖G中不含與中不含與K5同胚的子圖同胚的子圖, 也不也不含與含與K3,3同胚的子圖同胚的子圖.定理定理 G是平面圖是平面圖G中無可收縮為中無可收縮為K5的子圖的子圖, 也無也無可收縮為可收縮為K3,3的子圖的子圖. 15非平面圖證明非平面圖證明例例 證明下述證明下述2個(gè)圖均為非平面圖個(gè)圖均為非平面圖. 收縮收縮2

12、條邊條邊 收縮收縮2條邊條邊 K3,3取子圖取子圖K5取子圖取子圖16平面圖的對(duì)偶圖平面圖的對(duì)偶圖 定義定義 設(shè)平面圖設(shè)平面圖G, 有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn), m條邊和條邊和r個(gè)面?zhèn)€面, G的的對(duì)偶圖對(duì)偶圖G*=如下：如下：在在G的每一個(gè)面的每一個(gè)面Ri中任取一個(gè)點(diǎn)中任取一個(gè)點(diǎn)vi*作為作為G*的頂點(diǎn)的頂點(diǎn), V*= vi*| i=1,2,r .對(duì)對(duì)G每一條邊每一條邊ek, 若若ek在在G的面的面Ri與與Rj的公共邊界上的公共邊界上, 則作邊則作邊ek*=(vi*,vj*), 且與且與ek相交相交; 若若ek為為G中的橋且在中的橋且在面面Ri的邊界上的邊界上, 則作環(huán)則作環(huán)ek*=(vi*,vi*)

13、. E*= ek*| k=1,2, ,m . 17平面圖的對(duì)偶圖的實(shí)例平面圖的對(duì)偶圖的實(shí)例例例 黑色實(shí)線為原平面圖黑色實(shí)線為原平面圖, 紅色虛線為其對(duì)偶圖紅色虛線為其對(duì)偶圖 18平面圖的對(duì)偶圖的性質(zhì)平面圖的對(duì)偶圖的性質(zhì)性質(zhì)：性質(zhì)：對(duì)偶圖是平面圖，而且是平面嵌入對(duì)偶圖是平面圖，而且是平面嵌入.對(duì)偶圖是連通圖對(duì)偶圖是連通圖若邊若邊e為為G中的環(huán)，則中的環(huán)，則G*與與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為橋?yàn)闃? 若若e為橋，則為橋，則G*中與中與e對(duì)應(yīng)的邊對(duì)應(yīng)的邊e*為環(huán)為環(huán).同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu)同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu). 上頁兩個(gè)平面圖同構(gòu)上頁兩個(gè)平面圖同構(gòu), 它們的對(duì)偶圖不同構(gòu)它們的對(duì)偶圖不

14、同構(gòu). 19地圖地圖: 連通無橋平面圖的平面嵌入連通無橋平面圖的平面嵌入, 每一個(gè)面是一個(gè)每一個(gè)面是一個(gè)國(guó)家國(guó)家.若兩個(gè)國(guó)家有公共邊界若兩個(gè)國(guó)家有公共邊界,則稱則稱它們它們是相鄰的是相鄰的. 地圖著色地圖著色(面著色面著色): 對(duì)地圖的每個(gè)國(guó)家涂一種顏色，對(duì)地圖的每個(gè)國(guó)家涂一種顏色，使相鄰的國(guó)家涂不同的顏色使相鄰的國(guó)家涂不同的顏色. 地圖著色問題地圖著色問題: 用盡可能少的顏色給地圖著色用盡可能少的顏色給地圖著色. 地圖著色可以轉(zhuǎn)化成平面圖的點(diǎn)著色地圖著色可以轉(zhuǎn)化成平面圖的點(diǎn)著色. 當(dāng)當(dāng)G中無橋時(shí)中無橋時(shí), G*中無環(huán)中無環(huán). G的面與的面與G*的頂點(diǎn)對(duì)應(yīng)的頂點(diǎn)對(duì)應(yīng), 且且G的兩個(gè)面相的兩個(gè)面相鄰當(dāng)且僅當(dāng)鄰當(dāng)且僅當(dāng)G*對(duì)應(yīng)的兩個(gè)頂點(diǎn)相鄰對(duì)應(yīng)的兩個(gè)頂點(diǎn)相鄰, 從而從而G的面著色的面著色等同于等同于G*的點(diǎn)著色的點(diǎn)著色. 地圖著色地圖著色地圖著色與平面圖的點(diǎn)著色地圖著色與平面圖的點(diǎn)著色20例例紅紅紅紅蘭蘭蘭蘭綠綠綠綠綠綠綠綠綠綠綠綠黃黃黃黃黃黃黃黃黃黃黃黃四色定理四色定理四色猜想四色猜想(100多年前多年前): 任何地圖都可以用任何地圖都可以用4種顏色著種顏色著色色, 即即任何平面圖都是任何平面圖都是4-可著色的可著色的.1890年希伍德證明五色定理年希伍德證明五色