離散數(shù)學(xué)課件圖論ppt課件(編輯修改稿)
2025-05-29 05:11 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 , l?3，則 證明：由定理 推論 K5, K3,3不是平面圖 . 63 ?? nm School of Information Science and Engineering 定理 設(shè) G為 n（ n?3）階 m條邊的簡(jiǎn)單平面圖，則 m?3n?6. 證明：設(shè) G有 k（ k?1）個(gè)連通分支，若 G為樹(shù)或森林，當(dāng) n?3時(shí)， m?3n?6為真 . 否則 G中含圈，每個(gè)面至少由 l（ l?3）條邊圍成，又 2212 ???? lll定理 設(shè) G為 n（ n?3）階 m條邊的極大平面圖，則 m=3n?6. 證明：由定理 , 歐拉公式及定理 。 定理 設(shè) G 為簡(jiǎn)單平面圖，則 ?(G)?5. 證明： 階數(shù) n?6，結(jié)論為真。 當(dāng) n?7 時(shí)，用反證法。否則會(huì)推出 2m?6n ? m?3n，這與定理 . 與歐拉公式有關(guān)的定理 在 l=3達(dá)到最大值，由定理 m?3n?6. School of Information Science and Engineering 平面圖的判斷 1. 插入 2度頂點(diǎn)和消去 2度頂點(diǎn) 定義： (1) 消去 2度頂點(diǎn) v，見(jiàn)下圖中，由 (1) 到 (2) (2) 插入 2度頂點(diǎn) v，見(jiàn)下圖中，從 (2) 到 (1) . (1) (2) School of Information Science and Engineering 2. 圖之間的同胚 定義： 若 G1?G2，或經(jīng)過(guò)反復(fù)插入或消去 2度頂點(diǎn)后所得G?1?G?2，則稱(chēng) 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 平面圖的對(duì)偶圖 定義： 設(shè) G是某平面圖的某個(gè)平面嵌入，構(gòu)造 G的對(duì)偶圖 G*如下： (1) 在 G的面 Ri中放置 G*的頂點(diǎn) v*i. (2) 設(shè) e為 G的任意一條邊 . 若 e在 G的面 Ri與 Rj 的公共邊界上，做 G*的邊 e*與 e相 交，且 e*關(guān)聯(lián) G*的位于 Ri與 Rj中的頂點(diǎn) v*i與 v*j，即 e*=(v*i,v*j)， e*不與其它任何邊相交 . 若 e為 G中的橋且在面 Ri的邊界上，則 e*是以 Ri中 G*的頂 點(diǎn) v*i為端點(diǎn)的環(huán)，即 e*=(v*i,v*i). School of I
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1