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

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

2、)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.3平面圖和平面嵌入平面圖和平面嵌入( (續(xù)續(xù)) )今后稱一個圖是平面圖今后稱一個圖是平面圖, 可以是指定義中的平面圖可以是指定義中的平面圖, 又可以又可以是指平面嵌入是指平面嵌入, 視當時的情況而定視當時的情況而定. 當討論的問題與圖的畫當討論的問題與圖的畫法有關(guān)時法有關(guān)時, 是指平面嵌入是指平面嵌入. 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的邊將平面劃分成的每一個區(qū)域的邊將平面劃分成的每一個區(qū)域無限面無限面(外部面外部面): 面積無限的面面積無限的面, 用用R0表示表示有限面有限面(內(nèi)部面內(nèi)部面): 面積有限的面面積有限的面, 用用R1, R2, Rk表示表示 面面Ri的邊界的邊界: 包圍包圍Ri的所有邊構(gòu)成的回路組的所有邊構(gòu)成的回路組面面Ri的次數(shù)的次數(shù): Ri邊界的長度，用邊界的長度，用deg(Ri)表示表示 定理定理 平面圖各面的次數(shù)之和等于邊數(shù)的平面圖各面的次數(shù)之

4、和等于邊數(shù)的2倍倍.證證 每條邊可能在兩個面的公共邊界上，也可能只在一個面每條邊可能在兩個面的公共邊界上，也可能只在一個面的邊界上的邊界上. 前者前者, 在每個面的邊界上這條邊只出現(xiàn)一次在每個面的邊界上這條邊只出現(xiàn)一次, 計算計算兩次兩次. 后者后者, 它它在在這個這個面的邊界上出現(xiàn)面的邊界上出現(xiàn)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)中是

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

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

7、圖必為簡單圖極小非平面圖必為簡單圖例如例如, K5, K3,3是極小非平面圖是極小非平面圖9歐拉公式歐拉公式 定理定理 (歐拉公式歐拉公式) 設(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中有一個中有一個1度頂點度頂點v, 則則G =G-v 連通連通, 有有n-1個頂點個頂點, k條邊和條邊和r個面?zhèn)€面. 由由歸納假設(shè)歸納假設(shè), (n-1)-k+r=2, 即即n

8、-(k+1)+r=2, 得證得證m=k+1時結(jié)論成立時結(jié)論成立. (2) 否則否則, G中必有圈中必有圈. 刪除一個圈上的一條邊刪除一個圈上的一條邊,記作記作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 個連通分支有個連通分支有 ni個頂

9、點個頂點, mi 條邊和條邊和 ri 個面?zhèn)€面. 對各連通分支用歐拉公式對各連通分支用歐拉公式, 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條邊的連通平面圖條邊的連通平面圖, 每個面的次數(shù)不小于每個面的次數(shù)不小于l (l 3), 則則 設(shè)設(shè)G為有為有 p (p 2) 個連通分支的平面圖個連通分支的平面圖, 且每個面的次數(shù)不且每個面的次數(shù)不小于小于l (l 3), 則則證證 由各面次數(shù)之和等于邊數(shù)的由各面次數(shù)之和等

10、于邊數(shù)的2倍及歐拉公式得倍及歐拉公式得 2m lr = l (2+m-n)可解得所需結(jié)論可解得所需結(jié)論. 對對 p (p 2) 個連通分支的情況類似可證個連通分支的情況類似可證.)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度頂點度頂點v 如上圖從如上圖從(1)到到(

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

12、條邊條邊 收縮收縮2條邊條邊 K3,3取子圖取子圖K5取子圖取子圖16平面圖的對偶圖平面圖的對偶圖 定義定義 設(shè)平面圖設(shè)平面圖G, 有有n個頂點個頂點, m條邊和條邊和r個面?zhèn)€面, 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*=(vi*,vi*)

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

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