離散數(shù)學(xué)課件：第6章 特殊的圖2

1、16.4 平面圖平面圖 平面圖與平面嵌入平面圖與平面嵌入平面圖的面平面圖的面極大平面圖與極小非平面圖極大平面圖與極小非平面圖歐拉公式歐拉公式平面圖的對(duì)偶圖平面圖的對(duì)偶圖地圖著色與四色定理地圖著色與四色定理 2平面圖和平面嵌入平面圖和平面嵌入 定義定義 如果圖如果圖G 能以各能以各邊不交叉的形式邊不交叉的形式在平面上畫出在平面上畫出, 則稱則稱G是是平面圖平面圖. 這個(gè)無邊交叉的畫法稱作這個(gè)無邊交叉的畫法稱作G的的平平面嵌入面嵌入. 不能畫成平面嵌入的圖稱作不能畫成平面嵌入的圖稱作非平面圖非平面圖. 例如例如 下圖中下圖中(1)(4)是平面圖是平面圖, (2)是是(1)的平面嵌入，的平面嵌入，(

2、4)是是(3)的平面嵌入的平面嵌入. (5)是非平面圖是非平面圖.3平面圖和平面嵌入平面圖和平面嵌入( (續(xù)續(xù)) ) 有時(shí)稱一個(gè)圖是平面圖有時(shí)稱一個(gè)圖是平面圖, 是強(qiáng)調(diào)其符合定義是強(qiáng)調(diào)其符合定義, 而有時(shí)強(qiáng)調(diào)而有時(shí)強(qiáng)調(diào)的是平面嵌入畫法。的是平面嵌入畫法。 視當(dāng)時(shí)的情況而定視當(dāng)時(shí)的情況而定. 當(dāng)討論的問題與當(dāng)討論的問題與圖的畫法有關(guān)時(shí)圖的畫法有關(guān)時(shí), 指平面嵌入指平面嵌入. K5和和K3,3非平面圖非平面圖若若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ū)域 （這些區(qū)域內(nèi)既無這些區(qū)域內(nèi)既無G的頂，也無的頂，也無G的邊）的邊）無限面無限面(外部面外部面): 面積無限的面面積無限的面, 用用R0表示表示有限面有限面(內(nèi)部面內(nèi)部面): 面積有限的面面積有限的面, 用用R1, R2, Rk表示表示 面的邊界面的邊界: 包圍包圍Ri的所有邊的所有邊構(gòu)成的構(gòu)成的回路組回路組面的次數(shù)面的次數(shù): Ri邊界的長度，用邊界的長度，用deg(Ri)

4、表示表示 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)中是中是外部面外部面, 在在(2)中是內(nèi)部面中是內(nèi)部面; R2在在(1)中是內(nèi)部面中是內(nèi)部面, 在在(2)中是中是外部面外部面. 其實(shí)其實(shí), 在平面嵌入中在平面嵌入中可把任何面作為外部面可把任何面作為外部面.定理定理6.9 平面圖平面圖所有面所有面的次數(shù)之和等于邊數(shù)的的次數(shù)之和等于邊數(shù)的2倍倍.（可看作另可看作另一種握手定理

5、一種握手定理）【證證】 每條邊或在兩個(gè)面的公共邊界上，或僅在一個(gè)面的邊界上. 前者,這條邊在每個(gè)面的邊界上均出現(xiàn)一次, 從而計(jì)算兩次；后者, 它作為這個(gè)面的邊界出現(xiàn)2次, 也計(jì)算兩次. 67歐拉公式歐拉公式 定理定理6.11 (歐拉公式歐拉公式) 設(shè)設(shè)G為為n階階m條邊條邊r個(gè)面的個(gè)面的連通連通平面圖平面圖, 則則 n m+r=2. 【證證】 對(duì)邊數(shù)對(duì)邊數(shù)m做歸納證明做歸納證明. (1) m=0, 連通圖連通圖G為平凡圖為平凡圖 , 結(jié)論為真結(jié)論為真. (2) 設(shè)設(shè)m=k(k 0)結(jié)論為真結(jié)論為真, m=k+1時(shí)分情況討論如下時(shí)分情況討論如下: (i) 若若G中存在中存在1度的頂度的頂v, 則

6、則G =G-v 仍仍連通連通, 且是且是n-1個(gè)頂個(gè)頂點(diǎn)點(diǎn), k條邊和條邊和r個(gè)面的平面圖個(gè)面的平面圖. 由由歸納假設(shè)歸納假設(shè), (n-1)-k+r=2, 即即n-(k+1)+r=2； (ii) 否則否則, 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é)論也成立. 由由(1)(2) 定理得證定理得證. 8歐拉公式歐拉公式( (續(xù)續(xù)) )推論推論(

7、歐拉公式的推廣歐拉公式的推廣) 設(shè)設(shè)G是有是有 p (p 2) 個(gè)連通分支個(gè)連通分支的平面圖的平面圖, 則則 n m + r = p + 1【證證】 設(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 + 19平面圖的性質(zhì)平面圖的性質(zhì))2(2 nllm定理定理6.12 設(shè)設(shè)G為為n階階m條邊的連通平面圖條邊的連通平面圖, 每面的次數(shù)不小于每面的次數(shù)不

8、小于l (l 3), 則則 設(shè)設(shè)G為有為有 p (p 2) 個(gè)連通分支的平面圖個(gè)連通分支的平面圖, 且每個(gè)面的次數(shù)不且每個(gè)面的次數(shù)不小于小于l (l 3), 則則【證證】 由各面次數(shù)總和等于邊數(shù)的由各面次數(shù)總和等于邊數(shù)的2倍，及歐拉公式得倍，及歐拉公式得 2m lr = l (2+m-n) 可解得所需結(jié)論可解得所需結(jié)論. 對(duì)對(duì) p (p 2) 個(gè)連通分支的情況類似可證個(gè)連通分支的情況類似可證.)1(2 pnllm推論：推論：具有至少三個(gè)頂點(diǎn)的具有至少三個(gè)頂點(diǎn)的連通平面連通平面單單圖圖G，必有頂點(diǎn)，必有頂點(diǎn)u 滿滿足足d(u)5.【證證】 設(shè)設(shè)G=, |V|=v, |E|=e, G中中各面次數(shù)至

9、少為各面次數(shù)至少為3，由定理由定理6.12 推知：推知： e 3(v-2)/(3-2)= 3v-6若若 G 的所有頂點(diǎn)度的所有頂點(diǎn)度 d(ui) 6 則依據(jù)握手定理，又有：則依據(jù)握手定理，又有： 2e =d(ui) 6v ,即即 e 3v 3v-6 . 矛盾！矛盾！ G必須有頂點(diǎn)必須有頂點(diǎn)u 滿足滿足d(u)5.1011平面圖的性質(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,

10、39)25(23310 8)26(2449 12極大平面圖極大平面圖 定義定義 若若G是是簡單簡單平面圖平面圖, 并且任意在兩個(gè)并且任意在兩個(gè)不相鄰的頂點(diǎn)不相鄰的頂點(diǎn)之之間加一條新邊所得圖為非平面圖間加一條新邊所得圖為非平面圖, 則稱則稱G為為極大平面圖極大平面圖.例如例如, K5若刪去一條邊是極大平面圖若刪去一條邊是極大平面圖. ( K3,3 刪去一邊呢刪去一邊呢? ) K1, K2, K3, K4都是極大平面圖都是極大平面圖(它們已無不相鄰頂點(diǎn)它們已無不相鄰頂點(diǎn)).定理定理6.10 n(n 3)階階簡單簡單平面圖是平面圖是極大平面圖極大平面圖當(dāng)且僅當(dāng)且僅當(dāng)它當(dāng)它連通連通且各面的且各面的次數(shù)

11、都為次數(shù)都為3. 13【證證】必要性明顯，僅證充分性必要性明顯，僅證充分性若若n階簡單平面圖階簡單平面圖G連通，且每面次均為連通，且每面次均為3， 設(shè)其邊數(shù)為設(shè)其邊數(shù)為m，面數(shù)為，面數(shù)為r. 由定理由定理6.9 2m=3r ，依歐拉公式又有，依歐拉公式又有 n-m+r=2， 從而推得從而推得 m= 3n-6,根據(jù)根據(jù) 定理定理6.12， 此平面圖的邊數(shù)已達(dá)上限，此平面圖的邊數(shù)已達(dá)上限， 再加一再加一邊必不為平面圖邊必不為平面圖. 于是于是G為極大平面圖為極大平面圖一些一些結(jié)論結(jié)論極大平面圖必連通極大平面圖必連通. （否則在連通分支之間加邊仍是（否則在連通分支之間加邊仍是平面圖）平面圖）階數(shù)大于

12、等于階數(shù)大于等于3的極大平面圖中不可能有割點(diǎn)和橋的極大平面圖中不可能有割點(diǎn)和橋.階數(shù)大于等于階數(shù)大于等于4的極大平面圖均有的極大平面圖均有(G)3.14實(shí)例實(shí)例例例 是否是極大平面圖是否是極大平面圖? 利用定理利用定理6.10判斷判斷不是不是不是不是是是15極小非平面圖極小非平面圖 定義定義 若若G是非平面圖是非平面圖, 但任意刪除一條邊所得圖但任意刪除一條邊所得圖都是平面圖都是平面圖, 則稱則稱G為為極小非平面圖極小非平面圖. 極小非平面圖必為極小非平面圖必為簡單簡單圖圖例例, K5, K3,3是極小非平面圖是極小非平面圖16平面圖的一般判定：平面圖的一般判定：庫拉圖斯基定理庫拉圖斯基定理同

13、胚與收縮同胚與收縮消去消去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 ：如圖從：如圖從(1)到到(2)17庫拉圖斯基庫拉圖斯基定理定理 （1） G是平面圖是平面圖G中中不含不含與與K5同胚的子圖同胚的子圖, 也不也不含與含與K3,3同胚的子圖同胚的子圖.（2） G是平面圖是平面圖 G中中無無可收縮為可收縮為K5的子圖的子圖, 也無也無可收縮為可收縮為K3,3的子圖的子圖. 18非平面圖證明非平面圖證明例

14、例 證明下述證明下述2個(gè)圖均為非平面圖個(gè)圖均為非平面圖. 收縮收縮2條邊條邊 收縮收縮2條邊條邊 K3,3取子圖取子圖K5取子圖取子圖19平面圖的對(duì)偶圖平面圖的對(duì)偶圖 定義定義 設(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)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中的橋且

15、為面中的橋且為面Ri的邊界的邊界, 則作環(huán)則作環(huán)ek*=(vi*,vi*) 穿過穿過ek，得得 E*= ek*| k=1,2, ,m . 20平面圖的對(duì)偶圖的實(shí)例平面圖的對(duì)偶圖的實(shí)例例例 黑色實(shí)線為原平面圖黑色實(shí)線為原平面圖, 紅色虛線為其對(duì)偶圖紅色虛線為其對(duì)偶圖 21平面圖的對(duì)偶圖的性質(zhì)平面圖的對(duì)偶圖的性質(zhì)對(duì)偶圖性質(zhì)：對(duì)偶圖性質(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)

16、的平面圖的對(duì)偶圖不一定同構(gòu). 前例兩個(gè)平面圖同構(gòu)前例兩個(gè)平面圖同構(gòu), 它們的對(duì)偶圖不同構(gòu)它們的對(duì)偶圖不同構(gòu). 22地圖地圖: 連通無橋連通無橋平面圖的平面嵌入平面圖的平面嵌入, 每一個(gè)面是一個(gè)每一個(gè)面是一個(gè)國家國家.若兩個(gè)國家有公共邊界若兩個(gè)國家有公共邊界,則稱則稱它們它們是相鄰的是相鄰的. 地圖著色地圖著色(面著色面著色): 對(duì)地圖的每個(gè)國家涂一種顏色，對(duì)地圖的每個(gè)國家涂一種顏色，使相鄰的國家涂不同的顏色使相鄰的國家涂不同的顏色. 地圖著色問題地圖著色問題: 用盡可能少的顏色給地圖著色用盡可能少的顏色給地圖著色. 地圖著色可以地圖著色可以轉(zhuǎn)化成轉(zhuǎn)化成平面圖的平面圖的點(diǎ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)著色23例例紅紅紅紅蘭蘭蘭蘭綠綠綠綠綠綠綠綠綠綠綠綠黃黃黃黃黃黃黃黃黃黃黃黃四色定理四色定理四色猜想四色猜想(100多年前多年前): 任何地圖都可以用任何地圖都可以用4種顏色著種顏色著色色, 即即任何平面圖都是任何平面圖都是4-可著色的