離散數(shù)學第十七章平面(編輯修改稿)
2025-02-12 20:38 本頁面
【文章內容簡介】 n?6. 證 設 G有 k（ k?1）個連通分支，若 G為樹或森林，當 n?3時，m?3n?6為真 . 否則 G中含圈，每個面至少由 l（ l?3）條邊圍成，又 2212 ???? lll定理 設 G為 n（ n?3）階 m條邊的極大平面圖，則 m=3n?6. 證 由定理 , 歐拉公式及定理 . 定理 設 G 為簡單平面圖，則 ?(G)?5. 證 階數(shù) n?6，結論為真 . 當 n?7 時，用反證法 . 否則會推出2m?6n ? m?3n，這與定理 . 與歐拉公式有關的定理 在 l=3達到最大值，由定理 m?3n?6. 14 平面圖的判斷 1. 插入 2度頂點和消去 2度頂點 定義 (1) 消去 2度頂點 v，見下圖中，由 (1) 到 (2) (2) 插入 2度頂點 v，見下圖中，從 (2) 到 (1) . (1) (2) 15 2. 收縮邊 e，見下圖所示 . 3. 圖之間的同胚 定義 若 G1?G2，或經(jīng)過反復插入或消去 2度頂點后所得 G?1?G?2，則稱 G1與 G2同胚 . 圖的同胚 右邊兩個圖同胚 16 平面圖判定定理 定理 G是平面圖 ? G中不含與 K5或 K3,3同胚的子圖 . 定理 G是平面圖 ? G中無可收縮為 K5或 K3,3的子圖 例 1 證明所示圖 (1)與 (2)均為非平面圖 . (1) (2) 右圖 (1),(2)分別為 原圖 (1), (2)的子圖 與 K3,3, K5同胚 . 子圖 (1) (2) 17 平面圖的對偶圖 定義 設 G是某平面圖的某個平面嵌入，構造 G的對偶圖 G*如下： (1) 在 G的面 Ri中放置 G*的頂點 v*i. (2) 設 e為 G的任意一條邊 . 若 e在 G的面 Ri與 Rj 的公共邊界上，做 G*的邊 e*與 e相 交，且 e*關聯(lián) G*的位于 Ri與 Rj中的頂點 v*i與 v*j，即 e*=(v*i,v*j)， e*不與其它任何邊相交 . 若 e為 G中的橋且在面 Ri的邊界上，則 e*是以 Ri中 G*的頂 點 v*i為端點的環(huán)，即 e*=(v*i,v*i). 18 下面兩圖中，實線邊圖為平面圖，虛線邊圖為其對偶圖 . 實例 19 G 的對偶圖 G*有以下性質： (1) G*是平面圖，而且是平面嵌入 . (2) G*是連通圖 (3) 若邊 e為 G中的環(huán)，則 G*與 e對應的邊 e*為橋，若 e為橋，則 G*中與 e對應的
范文總結相關推薦
鄂ICP備17016276號-1