第14節(jié) 平面圖

1、集合集合論論 與圖論與圖論 1 第第14節(jié)節(jié) 平面圖平面圖 主要內(nèi)容：主要內(nèi)容： l 平面圖的基本概念平面圖的基本概念 l 歐拉公式歐拉公式 l 平面圖的判斷平面圖的判斷(庫(kù)拉托斯基定理庫(kù)拉托斯基定理) l 平面圖的對(duì)偶圖平面圖的對(duì)偶圖 集合集合論論 與圖論與圖論 2 1 平面圖的基本概念平面圖的基本概念 定義定義1 圖圖G稱(chēng)為稱(chēng)為被嵌入平面被嵌入平面S內(nèi)內(nèi)，如果，如果G的圖解的圖解 已畫(huà)在平面已畫(huà)在平面S上，而且任何兩條邊均不相交上，而且任何兩條邊均不相交(除頂點(diǎn)外除頂點(diǎn)外). 已嵌入平面的圖稱(chēng)為已嵌入平面的圖稱(chēng)為平面圖平面圖. 如果一個(gè)圖可以嵌入平面，則稱(chēng)此如果一個(gè)圖可以嵌入平面，則稱(chēng)此圖

2、是可平面的圖是可平面的. (1) (2) (3) (4) 在圖中，在圖中，(2)是是(1) 的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入. 集合集合論論 與圖論與圖論 3 幾點(diǎn)說(shuō)明及一些簡(jiǎn)單結(jié)論幾點(diǎn)說(shuō)明及一些簡(jiǎn)單結(jié)論 一般所談平面圖不一定是指平面嵌入一般所談平面圖不一定是指平面嵌入. 但討論但討論 某些性質(zhì)時(shí)，是指平面嵌入某些性質(zhì)時(shí)，是指平面嵌入. 結(jié)論：結(jié)論： (1) K5, K3,3都不是平面圖都不是平面圖(待證待證). (2) 設(shè)設(shè)GG，若，若G為平面圖，則為平面圖，則G 也是平面圖也是平面圖. 由此可知，由此可知，Kn(n4)，K2,n(n 1) 都是平面圖都是平面圖.

3、 (3) 設(shè)設(shè)GG，若，若G 為非平面圖，則為非平面圖，則G也是非平面圖也是非平面圖. 由此可知，由此可知，Kn(n 5)，Km,n(m,n 3) 都是非平面圖都是非平面圖. (4) 平行邊與環(huán)不影響平面性平行邊與環(huán)不影響平面性. 集合集合論論 與圖論與圖論 4 定義定義2 平面圖把平面分成了若干個(gè)區(qū)域，這平面圖把平面分成了若干個(gè)區(qū)域，這 些區(qū)域都是單連通的，稱(chēng)之為些區(qū)域都是單連通的，稱(chēng)之為G的面的面，其中無(wú)界的那，其中無(wú)界的那 個(gè)連通區(qū)域稱(chēng)為個(gè)連通區(qū)域稱(chēng)為G的外部面的外部面，其余的單連通區(qū)域稱(chēng)為，其余的單連通區(qū)域稱(chēng)為 G的內(nèi)部面的內(nèi)部面。 平面圖的內(nèi)部面與外部面平面圖的內(nèi)部面與外部面 集合集

4、合論論 與圖論與圖論 5 平面圖的每個(gè)內(nèi)部面都是平面圖的每個(gè)內(nèi)部面都是G的某個(gè)圈圍成的單連的某個(gè)圈圍成的單連 通區(qū)域。通區(qū)域。 沒(méi)有圈的圖沒(méi)有內(nèi)部面，只有一個(gè)外部面。沒(méi)有圈的圖沒(méi)有內(nèi)部面，只有一個(gè)外部面。 平面圖的內(nèi)部面與外部面平面圖的內(nèi)部面與外部面 集合集合論論 與圖論與圖論 6 (2) 面面 Ri 的邊界的邊界包圍包圍Ri的閉通道組的閉通道組 (3) 面面 Ri 的次數(shù)的次數(shù)Ri邊界的長(zhǎng)度邊界的長(zhǎng)度 幾點(diǎn)補(bǔ)充幾點(diǎn)補(bǔ)充 (1)若平面圖若平面圖G有有k個(gè)面，可用個(gè)面，可用R1, R2, , Rk表示表示. (4) 閉通道組是指：邊界可能是閉通道組是指：邊界可能是 圈，也可能是閉通圈，也可能是閉

5、通 道道. 特別地，還可能是非連通的閉通道之并特別地，還可能是非連通的閉通道之并. 定理定理 平面圖各面次數(shù)之和等于邊數(shù)的兩倍平面圖各面次數(shù)之和等于邊數(shù)的兩倍. 集合集合論論 與圖論與圖論 7 平面圖有平面圖有4個(gè)面，個(gè)面， deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 請(qǐng)寫(xiě)各面的邊界請(qǐng)寫(xiě)各面的邊界. 實(shí)實(shí) 例例 集合集合論論 與圖論與圖論 8 說(shuō)明說(shuō)明：若簡(jiǎn)單平面圖：若簡(jiǎn)單平面圖G中已無(wú)不相鄰頂點(diǎn)，中已無(wú)不相鄰頂點(diǎn)，G顯然是顯然是 極大平面圖，如極大平面圖，如K1(平凡圖平凡圖), K2, K3, K4都是極大平面圖都是極大平面圖. 極大極大( (最

6、大最大) )平面圖平面圖 定義定義3 若在若在(簡(jiǎn)單簡(jiǎn)單)平面圖平面圖G中的任意兩個(gè)不相鄰中的任意兩個(gè)不相鄰 的頂點(diǎn)之間加一條新邊所得圖為非平面圖，則稱(chēng)的頂點(diǎn)之間加一條新邊所得圖為非平面圖，則稱(chēng)G 為為極大平面圖極大平面圖. (1) (2) (3) 上圖中，只有上圖中，只有(3)為極大平面圖為極大平面圖. 集合集合論論 與圖論與圖論 9 極大平面圖的主要性質(zhì)：極大平面圖的主要性質(zhì)： 性質(zhì)性質(zhì)1 極大平面圖是連通的極大平面圖是連通的. 性質(zhì)性質(zhì)2 n(n 3)階極大平面圖中不可能有割點(diǎn)和橋階極大平面圖中不可能有割點(diǎn)和橋. 證明：證明：G中若有橋，則一定有割點(diǎn)，因而只需證無(wú)中若有橋，則一定有割點(diǎn)，

7、因而只需證無(wú) 割點(diǎn)即可割點(diǎn)即可. (用反證法用反證法.) 極大平面圖的性質(zhì)極大平面圖的性質(zhì) 集合集合論論 與圖論與圖論 10 定理定理1(歐拉公式歐拉公式) 如果一個(gè)平面連通圖有如果一個(gè)平面連通圖有p個(gè)個(gè) 頂點(diǎn)、頂點(diǎn)、q條邊、條邊、f個(gè)面，則個(gè)面，則p-q+f=2. 證明定理證明定理1： 對(duì)面數(shù)用歸納法對(duì)面數(shù)用歸納法. 當(dāng)當(dāng)f=1時(shí)，時(shí)，G沒(méi)有內(nèi)部面，所以沒(méi)有內(nèi)部面，所以G中無(wú)圈，中無(wú)圈，G是樹(shù)是樹(shù). p-q+f=1+1=2 假如對(duì)一切不超過(guò)假如對(duì)一切不超過(guò)f-1個(gè)面的平面連通圖歐拉公式個(gè)面的平面連通圖歐拉公式 成立，現(xiàn)證成立，現(xiàn)證f個(gè)面時(shí)的情況個(gè)面時(shí)的情況. 歐拉公式歐拉公式 定理定理2 (

8、歐拉公式的推廣歐拉公式的推廣)設(shè)設(shè)G是具有是具有k(k 2)個(gè)連個(gè)連 通分支的平面圖，則通分支的平面圖，則n m+r=k+1. 集合集合論論 與圖論與圖論 11 f2，G至少有一個(gè)內(nèi)部面，從而至少有一個(gè)內(nèi)部面，從而G中有一個(gè)圈中有一個(gè)圈. 這個(gè)內(nèi)部面是由這個(gè)圈圍成的，從這個(gè)圈上去掉一這個(gè)內(nèi)部面是由這個(gè)圈圍成的，從這個(gè)圈上去掉一 條邊條邊x，則打通了兩個(gè)面，則打通了兩個(gè)面. G-x有有p個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，q-1條邊，條邊，f-1個(gè)面?zhèn)€面. 由歸納假設(shè)知：由歸納假設(shè)知： p-(q-1)+(f-1)=2即：即：p-q+f=2 因此面數(shù)是因此面數(shù)是f時(shí)也成立時(shí)也成立. 歐拉公式歐拉公式 集合集合論論 與

9、圖論與圖論 12 推論推論1 若平面連通圖若平面連通圖G有有p個(gè)頂點(diǎn)個(gè)頂點(diǎn)q條邊且每個(gè)條邊且每個(gè) 面都是由長(zhǎng)為面都是由長(zhǎng)為n的圈圍成的，則的圈圍成的，則q=n(p-2)/(n-2). 證證 因?yàn)橐驗(yàn)镚的每個(gè)面都是長(zhǎng)為的每個(gè)面都是長(zhǎng)為n的圈圍成的，所的圈圍成的，所 以以G的每條邊都在的每條邊都在G的兩個(gè)面上的兩個(gè)面上. q=f n/2 f=2q/n p-q+2q/n=2 q=n(p-2)/(n-2) 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 集合集合論論 與圖論與圖論 13 推論推論2 設(shè)設(shè)G是一個(gè)有是一個(gè)有p個(gè)頂點(diǎn)個(gè)頂點(diǎn)q條邊的極大平面圖，條邊的極大平面圖， 則則G的每個(gè)面都是三角形，且的每個(gè)

10、面都是三角形，且q=3p-6，p3。 證證 若若G的一個(gè)面不是三角形的一個(gè)面不是三角形, (1)假如有兩點(diǎn)不相鄰，則假如有兩點(diǎn)不相鄰，則 在此面中把不相鄰的兩頂點(diǎn)連在此面中把不相鄰的兩頂點(diǎn)連 接起來(lái)，不影響平面性。接起來(lái)，不影響平面性。矛盾！矛盾！ 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 (2)假如圈上每?jī)牲c(diǎn)都相鄰假如圈上每?jī)牲c(diǎn)都相鄰; 若若v1,v3和和v2,v4在在G中都相鄰中都相鄰, 可以看到這兩個(gè)邊不可能不相交可以看到這兩個(gè)邊不可能不相交. 綜合以上情況，極大平面圖的每個(gè)面都是三角形綜合以上情況，極大平面圖的每個(gè)面都是三角形. 集合集合論論 與圖論與圖論 14 推論推論3 設(shè)設(shè)G是一

11、個(gè)是一個(gè)(p,q)可平面連通圖，而且可平面連通圖，而且G 的每個(gè)面都是一個(gè)長(zhǎng)為的每個(gè)面都是一個(gè)長(zhǎng)為4的圈圍成的，則的圈圍成的，則q=2p-4. 推論推論4 若若G是任一有是任一有p個(gè)頂點(diǎn)個(gè)頂點(diǎn)q條邊的可平面圖條邊的可平面圖, p3，則，則q3p-6. 若若G是是2-連通的且沒(méi)有三角形，則連通的且沒(méi)有三角形，則q2p-4. (1)因?yàn)楫?dāng)平面圖中每個(gè)面都是三角形時(shí)其邊數(shù)最因?yàn)楫?dāng)平面圖中每個(gè)面都是三角形時(shí)其邊數(shù)最 多，由推論多，由推論2，則，則q3p-6. (2)若若G是是2-連通的且沒(méi)有三角形，則連通的且沒(méi)有三角形，則G中任意兩個(gè)中任意兩個(gè) 頂點(diǎn)都在同一個(gè)圈上頂點(diǎn)都在同一個(gè)圈上. 已知沒(méi)有三角形，

12、所以圈的長(zhǎng)都是已知沒(méi)有三角形，所以圈的長(zhǎng)都是4時(shí)邊數(shù)最多時(shí)邊數(shù)最多. 所以所以q2p-4. 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 集合集合論論 與圖論與圖論 15 推論推論5 K5與與K3,3都不是可平面圖都不是可平面圖. 證證 如果如果K5是平面圖，則是平面圖，則5-10+f=2， 即即f=7. 每個(gè)面至少三條邊，每個(gè)面至少三條邊， 7個(gè)面至少需要個(gè)面至少需要21條邊條邊. 考慮到每條邊在兩個(gè)面上，考慮到每條邊在兩個(gè)面上， 2q3f，即，即 2021. 矛盾矛盾. 其實(shí)直接利用推論其實(shí)直接利用推論4，任意，任意(p,q)平面圖都滿(mǎn)足平面圖都滿(mǎn)足 q3p-6，這里，這里p3. q=103p

13、-6=9，這是不成立的，這是不成立的. 所以所以K5不是可平面圖不是可平面圖. 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 集合集合論論 與圖論與圖論 16 如果如果K3,3是平面圖，則是平面圖，則p-q+f=2， 即即6-9+f=2，亦即，亦即f=5. 在偶圖在偶圖K3,3中每個(gè)圈的長(zhǎng)至少為中每個(gè)圈的長(zhǎng)至少為 4，所以，所以2q4f=20，q10，但，但q=9， 矛盾矛盾. 所以所以K3,3不是平面圖不是平面圖. 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 集合集合論論 與圖論與圖論 17 推論推論6 每個(gè)平面圖每個(gè)平面圖G中頂點(diǎn)度的最小值不超中頂點(diǎn)度的最小值不超 過(guò)過(guò)5， 即即 (G)5. 如

14、果如果G的每個(gè)頂點(diǎn)的度大于的每個(gè)頂點(diǎn)的度大于5，也就是，也就是6， 由歐拉定理，由歐拉定理，2q6p，即，即q3p. 仍然用推論仍然用推論4，q3p-6. 那么所有頂點(diǎn)的度數(shù)和大于或等于那么所有頂點(diǎn)的度數(shù)和大于或等于6p. 不滿(mǎn)足推論不滿(mǎn)足推論4，q3p-6. 因此，每個(gè)平面圖因此，每個(gè)平面圖G中頂點(diǎn)度的最小值不超過(guò)中頂點(diǎn)度的最小值不超過(guò) 5，即，即 (G)5. 與歐拉公式有關(guān)的結(jié)論與歐拉公式有關(guān)的結(jié)論 集合集合論論 與圖論與圖論 18 例例1 頂點(diǎn)數(shù)頂點(diǎn)數(shù)p4的極大平面圖，的極大平面圖， (G)3. 證證 設(shè)設(shè)G是極大平面圖，其最小度頂點(diǎn)為是極大平面圖，其最小度頂點(diǎn)為v. 設(shè)設(shè)G-v也是一個(gè)

15、平面圖，也是一個(gè)平面圖，v在在G-v的一個(gè)面內(nèi)的一個(gè)面內(nèi). 在這個(gè)面內(nèi)，邊界上至少有三個(gè)頂點(diǎn)在這個(gè)面內(nèi)，邊界上至少有三個(gè)頂點(diǎn). 由極大性，由極大性，v必然與這些頂點(diǎn)都相連必然與這些頂點(diǎn)都相連. 因此，因此， (G)3. v 實(shí)實(shí) 例例 集合集合論論 與圖論與圖論 19 K5和和K3,3不是平面圖不是平面圖. 平面圖的每個(gè)子圖都是平面圖，因此，平面圖中不平面圖的每個(gè)子圖都是平面圖，因此，平面圖中不 含子圖含子圖K5和和K3,3. 定義定義4 設(shè)設(shè)x=uv是圖是圖G=(V,E)的一條邊，的一條邊，w不是不是G 的頂點(diǎn)，則當(dāng)用邊的頂點(diǎn)，則當(dāng)用邊uw和和wv代替邊代替邊x時(shí)，就稱(chēng)時(shí)，就稱(chēng)x被被細(xì)分細(xì)分

16、. 如果如果G的某些邊被細(xì)分，產(chǎn)生的圖稱(chēng)為的某些邊被細(xì)分，產(chǎn)生的圖稱(chēng)為G的的細(xì)分圖細(xì)分圖. u v 圖圖G x u v w G的細(xì)分的細(xì)分 圖圖 平面圖的判斷平面圖的判斷 集合集合論論 與圖論與圖論 20 定義定義5 兩個(gè)圖稱(chēng)為兩個(gè)圖稱(chēng)為同胚同胚的，如果它們都可以的，如果它們都可以 從同一個(gè)圖通過(guò)一系列的邊細(xì)分得到從同一個(gè)圖通過(guò)一系列的邊細(xì)分得到. 下面幾個(gè)圖是同胚的下面幾個(gè)圖是同胚的. 圖與圖之間同胚圖與圖之間同胚 v 圖圖G x v w G的細(xì)分的細(xì)分 圖圖 集合集合論論 與圖論與圖論 21 定義定義4 所定義的的細(xì)分也稱(chēng)為所定義的的細(xì)分也稱(chēng)為插入插入2度頂點(diǎn)度頂點(diǎn). 與之相對(duì)應(yīng)的還有一種

17、方法：與之相對(duì)應(yīng)的還有一種方法：消去消去2度頂點(diǎn)度頂點(diǎn). 補(bǔ)補(bǔ) 充充 (1) 消去消去2度頂點(diǎn)度頂點(diǎn)v，見(jiàn)下圖中，由，見(jiàn)下圖中，由(1) 到到(2) ； (2) 插入插入2度頂點(diǎn)度頂點(diǎn)v，見(jiàn)下圖中，從，見(jiàn)下圖中，從(2) 到到(1) . 定義定義5 若若G1 G2，或經(jīng)過(guò)反復(fù)插入或消去，或經(jīng)過(guò)反復(fù)插入或消去2 度頂點(diǎn)后所得度頂點(diǎn)后所得G 1 G 2，則稱(chēng)，則稱(chēng)G1與與G2同胚同胚. 集合集合論論 與圖論與圖論 22 定理定理3（庫(kù)拉托斯基（庫(kù)拉托斯基,1930）一個(gè)圖是可平面）一個(gè)圖是可平面 的充分必要條件是它沒(méi)有同胚于的充分必要條件是它沒(méi)有同胚于K5和和K3,3的子圖的子圖. 例例2 證明左

18、下圖不是可平面圖證明左下圖不是可平面圖. 因?yàn)樗信c因?yàn)樗信cK5同胚的子圖同胚的子圖. u v 庫(kù)拉托斯基定理庫(kù)拉托斯基定理 集合集合論論 與圖論與圖論 23 例例3 證明所示圖證明所示圖 (1)與與(2)均為非均為非 平面圖平面圖. (1) (2) 右圖右圖(1),(2)分別為分別為 原圖原圖(1), (2)的子圖的子圖 與與K3,3, K5同胚同胚. 子圖子圖 (1) 子圖子圖(2) 庫(kù)拉托斯基定理庫(kù)拉托斯基定理 集合集合論論 與圖論與圖論 24 定義定義6 一個(gè)圖一個(gè)圖G的一個(gè)的一個(gè)初等收縮初等收縮由合并兩個(gè)相鄰由合并兩個(gè)相鄰 的頂點(diǎn)的頂點(diǎn)u和和v得到，即從得到，即從G中去掉中去掉

19、u和和v，然后再加上，然后再加上 一個(gè)新頂點(diǎn)一個(gè)新頂點(diǎn)w，使得，使得w相鄰所有與相鄰所有與u或或v相鄰的頂點(diǎn)相鄰的頂點(diǎn). 一個(gè)圖一個(gè)圖G可收縮到圖可收縮到圖H，如果，如果H可以從可以從G經(jīng)一系列經(jīng)一系列 的初等收縮得到的初等收縮得到. 圖圖G的初等收縮的初等收縮 集合集合論論 與圖論與圖論 25 定理定理4 一個(gè)圖是可平面的當(dāng)且僅當(dāng)它沒(méi)有一個(gè)一個(gè)圖是可平面的當(dāng)且僅當(dāng)它沒(méi)有一個(gè) 可以收縮到可以收縮到K5或或K3,3的子圖的子圖. 例例2 證明左下圖不是可平面圖證明左下圖不是可平面圖. 因?yàn)樗梢允湛s到因?yàn)樗梢允湛s到K5 . 庫(kù)拉托斯基定理庫(kù)拉托斯基定理 集合集合論論 與圖論與圖論 26 定義定

20、義7 設(shè)設(shè)G=(V,E)是一個(gè)平面圖，由是一個(gè)平面圖，由G按如下方按如下方 法構(gòu)造一個(gè)圖法構(gòu)造一個(gè)圖G*，G*稱(chēng)為稱(chēng)為G的的對(duì)偶圖對(duì)偶圖: (3)如果某條邊如果某條邊x僅在一僅在一 個(gè)面中出現(xiàn)而不是兩個(gè)面的個(gè)面中出現(xiàn)而不是兩個(gè)面的 公共邊公共邊 (是不是橋？是不是橋？) ，則在，則在 G*中這個(gè)面對(duì)應(yīng)的頂點(diǎn)有一中這個(gè)面對(duì)應(yīng)的頂點(diǎn)有一 個(gè)環(huán)個(gè)環(huán). (1)對(duì)對(duì)G的每個(gè)面的每個(gè)面f對(duì)應(yīng)地有對(duì)應(yīng)地有G*的一個(gè)頂點(diǎn)的一個(gè)頂點(diǎn)f*； (2)對(duì)對(duì)G的每條邊的每條邊e對(duì)應(yīng)地有對(duì)應(yīng)地有G*的一條邊的一條邊e*：G*的兩的兩 個(gè)頂點(diǎn)個(gè)頂點(diǎn)f*與與g*由邊由邊e*聯(lián)結(jié)，當(dāng)且僅當(dāng)聯(lián)結(jié)，當(dāng)且僅當(dāng)G中與頂點(diǎn)中與頂點(diǎn)f*與與g*對(duì)對(duì) 應(yīng)的面應(yīng)的面f與與g有公共邊有公共邊e; 平面圖的對(duì)