離散數(shù)學課件圖論ppt課件(編輯修改稿)
2025-05-29 05:11 本頁面
【文章內容簡介】 , l?3，則 證明：由定理 推論 K5, K3,3不是平面圖 . 63 ?? nm School of Information Science and Engineering 定理 設 G為 n（ n?3）階 m條邊的簡單平面圖，則 m?3n?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. School of Information Science and Engineering 平面圖的判斷 1. 插入 2度頂點和消去 2度頂點 定義： (1) 消去 2度頂點 v，見下圖中，由 (1) 到 (2) (2) 插入 2度頂點 v，見下圖中，從 (2) 到 (1) . (1) (2) School of Information Science and Engineering 2. 圖之間的同胚 定義： 若 G1?G2，或經過反復插入或消去 2度頂點后所得G?1?G?2，則稱 G1與 G2同胚 . 圖的同胚 定理 (Kuratowski定理 ) G是平面圖 ? G中不含與 K5或K3,3同胚的子圖。 (1) (2) 子圖 (1) (2) School of Information Science and Engineering 平面圖判定定理 判斷下面彼得森 (Peterser)圖 : v1 v6 v2 v5 v8 v9 v3 v4 v7 v10 v1 v6 v2 v5 v8 v9 v3 v4 v7 v10 v1 v8 v9 v2 v6 v5 v10 v4 v3 v7 School of Information Science and Engineering 平面圖的對偶圖 定義： 設 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). School of I
教學課件相關推薦
鄂ICP備17016276號-1