第61講 平面圖

《第61講 平面圖》由會(huì)員分享，可在線閱讀，更多相關(guān)《第61講 平面圖（26頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、離散數(shù)學(xué)離散數(shù)學(xué)第第61講講 平面圖平面圖第第7章章 幾類特殊的圖幾類特殊的圖7.5 平面圖平面圖本講內(nèi)容本講內(nèi)容平面圖的有關(guān)概念平面圖的有關(guān)概念1Euler公式公式2Kuratowski定理定理3平面圖的對(duì)偶圖平面圖的對(duì)偶圖47.5 平面圖平面圖 本節(jié)僅討論無向圖本節(jié)僅討論無向圖. 單層印刷電路版、集成電路的布線等涉及單層印刷電路版、集成電路的布線等涉及平面圖平面圖. 平面圖與地圖著色問題也密切相關(guān)平面圖與地圖著色問題也密切相關(guān). 1. 平面圖的有關(guān)概念平面圖的有關(guān)概念 Def 設(shè)設(shè)G是無向圖是無向圖, 若可將若可將G畫在一個(gè)平面上畫在一個(gè)平面上, 使得任意兩條邊僅僅在節(jié)點(diǎn)處才相交使得任意兩

2、條邊僅僅在節(jié)點(diǎn)處才相交, 則稱則稱G是可平面圖或簡(jiǎn)稱是可平面圖或簡(jiǎn)稱G為為平面圖平面圖(planar graph). 不能畫在曲面上不能畫在曲面上? 平面表示平面表示? 由于一個(gè)平面圖與其平面表示是同構(gòu)的由于一個(gè)平面圖與其平面表示是同構(gòu)的, 因因此平面圖通常是指其平面表示此平面圖通常是指其平面表示. 兩個(gè)重要的非平面圖的例子兩個(gè)重要的非平面圖的例子: (1) K5. (2) K3,3. Def 設(shè)設(shè)G是平面圖是平面圖,由由G的若干條邊所圍成的的若干條邊所圍成的連通區(qū)域稱為圖連通區(qū)域稱為圖G的的面面(face), 圍成面的圍成面的(回回路所在的路所在的)邊稱為面的邊稱為面的邊界邊界(bounda

3、ry). 一個(gè)區(qū)域是連通的一個(gè)區(qū)域是連通的, 是指其內(nèi)部不包含該圖是指其內(nèi)部不包含該圖的任何邊的任何邊. 理解平面圖的面理解平面圖的面: 在一張較大的紙上將平面在一張較大的紙上將平面圖畫上圖畫上, 然后用剪刀將圖的所有邊剪破然后用剪刀將圖的所有邊剪破, 這這張紙被分成的每一部分就是一個(gè)面張紙被分成的每一部分就是一個(gè)面. 圍墻圍墻? 特別注意特別注意, 任何平面圖都有一個(gè)由若干條邊任何平面圖都有一個(gè)由若干條邊往外圍成的一個(gè)面往外圍成的一個(gè)面,它是唯一的一個(gè)它是唯一的一個(gè)無限面無限面. 平面圖的平面圖的兩個(gè)面相鄰兩個(gè)面相鄰是指這兩個(gè)面有公共是指這兩個(gè)面有公共的邊界的邊界. 2. Euler公式公式

4、 Theorem (Euler公式公式)任意任意(n, m)連通平面圖連通平面圖的面數(shù)的面數(shù)r = m n +2. Proof 對(duì)面數(shù)對(duì)面數(shù)r歸納歸納. r = 1. r 2 圈圈C. 去掉去掉C上的一條邊上的一條邊e. G e. Remark 在在Euler公式中公式中, “連通連通”的條件是的條件是必不可少的必不可少的. . 2) 1(1nmr Corollary 1 任意任意(n, m)簡(jiǎn)單平面圖簡(jiǎn)單平面圖, 若若n 3, 則則m 3n - 6. n3? 不妨設(shè)不妨設(shè)G連通連通, 否則考慮其連通分支否則考慮其連通分支. 由于對(duì)于由于對(duì)于n2(n7)的簡(jiǎn)單圖有的簡(jiǎn)單圖有m3n, 若存若存在

5、連通分支的節(jié)點(diǎn)個(gè)數(shù)在連通分支的節(jié)點(diǎn)個(gè)數(shù)n3, 就有邊數(shù)就有邊數(shù)m 3n 6, 結(jié)論成立結(jié)論成立. 假設(shè)每個(gè)假設(shè)每個(gè)連通分支的節(jié)點(diǎn)個(gè)連通分支的節(jié)點(diǎn)個(gè)數(shù)均數(shù)均2. 若存在兩個(gè)若存在兩個(gè)連通分支的節(jié)點(diǎn)個(gè)數(shù)為連通分支的節(jié)點(diǎn)個(gè)數(shù)為2, 則這則這兩個(gè)連通分支的邊數(shù)兩個(gè)連通分支的邊數(shù)2 34 6, 結(jié)論成立結(jié)論成立. 若若節(jié)點(diǎn)個(gè)數(shù)為節(jié)點(diǎn)個(gè)數(shù)為2的連通分支僅一個(gè)或沒有的連通分支僅一個(gè)或沒有,結(jié)結(jié)論也成立論也成立.2)2( 3mnm 例例7-16 證明證明: K5不是平面圖不是平面圖. Hint 反證反證. 10 35 6? Corollary 2 任意任意(n, m)簡(jiǎn)單平面圖簡(jiǎn)單平面圖, 若若G不不含含K3

6、子圖且子圖且n 3, 則則m 2n - 4. 例例7-17 證明證明: K3,3不是平面圖不是平面圖. Hint 反證反證. 9 26 4? 更一般的結(jié)論更一般的結(jié)論: 習(xí)題習(xí)題7.5 7.2)2(4mnm 下面的定理是證明下面的定理是證明“五色定理五色定理”的關(guān)鍵的關(guān)鍵. Theorem 任何簡(jiǎn)單平面圖必存在一個(gè)度數(shù)任何簡(jiǎn)單平面圖必存在一個(gè)度數(shù)5 的節(jié)點(diǎn)的節(jié)點(diǎn). Proof 不妨設(shè)不妨設(shè)n 3. 假設(shè)假設(shè) v V, deg(v) 6.).63(22)deg(6nmvnVv 3. Kuratowski定理定理 Def 若兩個(gè)圖是同構(gòu)的若兩個(gè)圖是同構(gòu)的, 或者通過反復(fù)進(jìn)行或者通過反復(fù)進(jìn)行以下操作

7、使得它們同構(gòu)以下操作使得它們同構(gòu), 則稱這兩個(gè)圖則稱這兩個(gè)圖同胚同胚(homeomorphism): Theorem (Kuratowski, 1930) 無向圖無向圖G是平是平面圖的充要條件是面圖的充要條件是G無同胚于無同胚于K5和和K3,3的子的子圖圖. 例例8-18 證明證明: Petersen圖不是平面圖圖不是平面圖. 習(xí)題習(xí)題7.5 5: 利用利用Euler公式證明公式證明. 4. 平面圖的對(duì)偶圖平面圖的對(duì)偶圖 對(duì)平面圖對(duì)平面圖G的面的研究可以轉(zhuǎn)換為對(duì)其對(duì)偶的面的研究可以轉(zhuǎn)換為對(duì)其對(duì)偶圖圖G*的節(jié)點(diǎn)的研究的節(jié)點(diǎn)的研究. 根據(jù)定義知根據(jù)定義知, 任意平面圖的對(duì)偶圖是平面圖任意平面圖的對(duì)偶圖是平面圖且是連通的且是連通的. 設(shè)設(shè)G是是(n, m)平面圖平面圖, 有有r個(gè)面?zhèn)€面, 則則G*是是(r, m)平面圖平面圖, G*有有n個(gè)面?zhèn)€面. 對(duì)于連通平面圖對(duì)于連通平面圖G, 其對(duì)偶圖為其對(duì)偶圖為G*, 這時(shí)這時(shí)G*的的對(duì)偶圖對(duì)偶圖G*為本身為本身. 對(duì)于非連通平面圖對(duì)于非連通平面圖G, 可可能能G與與G*不同構(gòu)不同構(gòu).小結(jié)與作業(yè)小結(jié)與作業(yè)理解平面圖的有關(guān)概念理解平面圖的有關(guān)概念掌握掌握Euler公式及其推論公式及其推論了解了解Kuratowski定理定理理解平面圖的對(duì)偶圖理解平面圖的對(duì)偶圖習(xí)題習(xí)題7.5 3, 4, 5作業(yè)作業(yè)Any Questions?