離散數(shù)學(xué)離散數(shù)學(xué)第第61講講 平面圖平面圖第第7章章 幾類特殊的圖幾類特殊的圖7.5 平面圖平面圖本講內(nèi)容本講內(nèi)容平面圖的有關(guān)概念平面圖的有關(guān)概念1Euler公式公式2Kuratowski定理定理3平面圖的對偶圖平面圖的對偶圖47.5 平面圖平面圖 本節(jié)僅討論無向圖本節(jié)僅討論無向圖. 單層印刷電路版、集成電路的布線等涉及單層印刷電路版、集成電路的布線等涉及平面圖平面圖. 平面圖與地圖著色問題也密切相關(guān)平面圖與地圖著色問題也密切相關(guān). 1. 平面圖的有關(guān)概念平面圖的有關(guān)概念 Def 設(shè)設(shè)G是無向圖是無向圖, 若可將若可將G畫在一個平面上畫在一個平面上, 使得任意兩條邊僅僅在節(jié)點處才相交使得任意兩條邊僅僅在節(jié)點處才相交, 則稱則稱G是可平面圖或簡稱是可平面圖或簡稱G為為平面圖平面圖(planar graph). 不能畫在曲面上不能畫在曲面上? 平面表示平面表示? 由于一個平面圖與其平面表示是同構(gòu)的由于一個平面圖與其平面表示是同構(gòu)的, 因因此平面圖通常是指其平面表示此平面圖通常是指其平面表示. 兩個重要的非平面圖的例子兩個重要的非平面圖的例子: (1) K5. (2) K3,3. Def 設(shè)設(shè)G是平面圖是平面圖,由由G的若干條邊所圍成的的若干條邊所圍成的連通區(qū)域稱為圖連通區(qū)域稱為圖G的的面面(face), 圍成面的圍成面的(回回路所在的路所在的)邊稱為面的邊稱為面的邊界邊界(boundary). 一個區(qū)域是連通的一個區(qū)域是連通的, 是指其內(nèi)部不包含該圖是指其內(nèi)部不包含該圖的任何邊的任何邊. 理解平面圖的面理解平面圖的面: 在一張較大的紙上將平面在一張較大的紙上將平面圖畫上圖畫上, 然后用剪刀將圖的所有邊剪破然后用剪刀將圖的所有邊剪破, 這這張紙被分成的每一部分就是一個面張紙被分成的每一部分就是一個面. 圍墻圍墻? 特別注意特別注意, 任何平面圖都有一個由若干條邊任何平面圖都有一個由若干條邊往外圍成的一個面往外圍成的一個面,它是唯一的一個它是唯一的一個無限面無限面. 平面圖的平面圖的兩個面相鄰兩個面相鄰是指這兩個面有公共是指這兩個面有公共的邊界的邊界. 2. Euler公式公式 Theorem (Euler公式公式)任意任意(n, m)連通平面圖連通平面圖的面數(shù)的面數(shù)r = m n +2. Proof 對面數(shù)對面數(shù)r歸納歸納. r = 1. r 2 圈圈C. 去掉去掉C上的一條邊上的一條邊e. G e. Remark 在在Euler公式中公式中, “連通連通”的條件是的條件是必不可少的必不可少的. . 2) 1(1nmr Corollary 1 任意任意(n, m)簡單平面圖簡單平面圖, 若若n 3, 則則m 3n - 6. n3? 不妨設(shè)不妨設(shè)G連通連通, 否則考慮其連通分支否則考慮其連通分支. 由于對于由于對于n2(n7)的簡單圖有的簡單圖有m3n, 若存若存在連通分支的節(jié)點個數(shù)在連通分支的節(jié)點個數(shù)n3, 就有邊數(shù)就有邊數(shù)m 3n 6, 結(jié)論成立結(jié)論成立. 假設(shè)每個假設(shè)每個連通分支的節(jié)點個連通分支的節(jié)點個數(shù)均數(shù)均2. 若存在兩個若存在兩個連通分支的節(jié)點個數(shù)為連通分支的節(jié)點個數(shù)為2, 則這則這兩個連通分支的邊數(shù)兩個連通分支的邊數(shù)2 34 6, 結(jié)論成立結(jié)論成立. 若若節(jié)點個數(shù)為節(jié)點個數(shù)為2的連通分支僅一個或沒有的連通分支僅一個或沒有,結(jié)結(jié)論也成立論也成立.2)2( 3mnm 例例7-16 證明證明: K5不是平面圖不是平面圖. Hint 反證反證. 10 35 6? Corollary 2 任意任意(n, m)簡單平面圖簡單平面圖, 若若G不不含含K3子圖且子圖且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 任何簡單平面圖必存在一個度數(shù)任何簡單平面圖必存在一個度數(shù)5 的節(jié)點的節(jié)點. Proof 不妨設(shè)不妨設(shè)n 3. 假設(shè)假設(shè) v V, deg(v) 6.).63(22)deg(6nmvnVv 3. Kuratowski定理定理 Def 若兩個圖是同構(gòu)的若兩個圖是同構(gòu)的, 或者通過反復(fù)進行或者通過反復(fù)進行以下操作使得它們同構(gòu)以下操作使得它們同構(gòu), 則稱這兩個圖則稱這兩個圖同胚同胚(homeomorphism): Theorem (Kuratowski, 1930) 無向圖無向圖G是平是平面圖的充要條件是面圖的充要條件是G無同胚于無同胚于K5和和K3,3的子的子圖圖. 例例8-18 證明證明: Petersen圖不是平面圖圖不是平面圖. 習(xí)題習(xí)題7.5 5: 利用利用Euler公式證明公式證明. 4. 平面圖的對偶圖平面圖的對偶圖 對平面圖對平面圖G的面的研究可以轉(zhuǎn)換為對其對偶的面的研究可以轉(zhuǎn)換為對其對偶圖圖G*的節(jié)點的研究的節(jié)點的研究. 根據(jù)定義知根據(jù)定義知, 任意平面圖的對偶圖是平面圖任意平面圖的對偶圖是平面圖且是連通的且是連通的. 設(shè)設(shè)G是是(n, m)平面圖平面圖, 有有r個面?zhèn)€面, 則則G*是是(r, m)平面圖平面圖, G*有有n個面?zhèn)€面. 對于連通平面圖對于連通平面圖G, 其對偶圖為其對偶圖為G*, 這時這時G*的的對偶圖對偶圖G*為本身為本身. 對于非連通平面圖對于非連通平面圖G, 可可能能G與與G*不同構(gòu)不同構(gòu).小結(jié)與作業(yè)小結(jié)與作業(yè)理解平面圖的有關(guān)概念理解平面圖的有關(guān)概念掌握掌握Euler公式及其推論公式及其推論了解了解Kuratowski定理定理理解平面圖的對偶圖理解平面圖的對偶圖習(xí)題習(xí)題7.5 3, 4, 5作業(yè)作業(yè)Any Questions?