《集合論與圖論課件10.1-平面圖的概念pdf.pdf》由會員分享，可在線閱讀，更多相關(guān)《集合論與圖論課件10.1-平面圖的概念pdf.pdf（17頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、單元單元10.1 平面圖的概念平面圖的概念 第二編第二編 圖論圖論 第十一章第十一章 平面圖平面圖 11.1 平面圖的基本概念平面圖的基本概念 內(nèi)容提要內(nèi)容提要 四色問題四色問題 平面圖平面圖、平面表示、球面表示、平面表示、球面表示 面、面的邊界、面的次數(shù)面、面的邊界、面的次數(shù) 極小非平面圖極小非平面圖 極大平面圖極大平面圖 四色問題四色問題 四色問題四色問題 四色問題四色問題 平面圖平面圖 在平面上邊與邊不在非頂點(diǎn)處相交的圖在平面上邊與邊不在非頂點(diǎn)處相交的圖 可平面圖可平面圖 可以畫在平面上可以畫在平面上,使得邊與邊不在非頂點(diǎn)處使得邊與邊不在非頂點(diǎn)處相交的圖相交的圖 平面嵌入平面嵌入 畫在平

2、面上使得邊與邊不在非頂點(diǎn)處相交畫在平面上使得邊與邊不在非頂點(diǎn)處相交 球面嵌入球面嵌入,曲面嵌入曲面嵌入 球面嵌入球面嵌入:畫在球面上使得邊與邊不在非頂畫在球面上使得邊與邊不在非頂點(diǎn)處相交點(diǎn)處相交 曲面嵌入曲面嵌入:畫在曲面上使得邊與邊不在非頂畫在曲面上使得邊與邊不在非頂點(diǎn)處相交點(diǎn)處相交,如環(huán)面嵌入如環(huán)面嵌入 定理定理11.1 定理定理11.1 11.1 可可平面嵌入平面嵌入 可球面嵌入可球面嵌入 證明證明 連續(xù)球極投影連續(xù)球極投影.#面面 區(qū)域區(qū)域:不含頂點(diǎn)與邊的極大連通曲面不含頂點(diǎn)與邊的極大連通曲面,R 外部外部區(qū)域區(qū)域:面積無限的區(qū)域面積無限的區(qū)域,R0 區(qū)域區(qū)域邊界邊界:與與R關(guān)聯(lián)的邊和

3、頂點(diǎn)構(gòu)成的關(guān)聯(lián)的邊和頂點(diǎn)構(gòu)成的子圖子圖,面面:區(qū)域及其邊界區(qū)域及其邊界 面的面的次數(shù)次數(shù):deg(R)=邊界長度邊界長度 R定理定理11.2 ri=1deg(Ri)=2m.#定理定理11.3 定理定理11.311.3 任何任何平面嵌入的內(nèi)部面都可以在另平面嵌入的內(nèi)部面都可以在另一種平面嵌入下成為外部面一種平面嵌入下成為外部面 證明證明:平面嵌入平面嵌入 球面嵌入球面嵌入 把該面旋轉(zhuǎn)到把該面旋轉(zhuǎn)到北極北極 平面嵌入平面嵌入.#極極大平面圖大平面圖 是平面圖是平面圖,但是在任意兩個不相鄰頂點(diǎn)之間但是在任意兩個不相鄰頂點(diǎn)之間加邊就是非平面圖加邊就是非平面圖 例如例如,K5刪除任意一邊刪除任意一邊 定理定理11.4 定理定理11.4 11.4 n(3)階簡單連通平面圖是極大平階簡單連通平面圖是極大平面圖面圖 R,deg(R)=3 證明證明:()簡單簡單圖圖 deg(R)3,極極大大平面圖平面圖 deg(R)3.()R,deg(R)=3 不能加邊而不交叉不能加邊而不交叉.#極小非平面圖極小非平面圖 是非平面圖是非平面圖,但是刪除任意但是刪除任意1邊就是平面圖邊就是平面圖 例如例如,K5,K3,3 K5 K3,3 小結(jié)小結(jié) 平面圖、平面表示、球面表示平面圖、平面表示、球面表示 面、面的邊界、面的次數(shù)面、面的邊界、面的次數(shù) 極極小非平面圖小非平面圖 極大平面圖極大平面圖