離散數(shù)學(xué)課件圖論ppt課件-在線瀏覽
2025-06-19 05:11本頁面
【正文】 圖可知， G每個面的 次數(shù)均 ?3. (2) 因為 G為平面圖，又為極 大平面圖 . 可證 G不可能 存在次數(shù) 3的面 . 就給出的圖討論即可 . 極大平面圖的性質(zhì) 定理 設(shè) G為 n（ n?3）階極大平面圖，則 G的每個面的 次數(shù)均為 3。 定理 ? 設(shè) G為 n (n?3) 階平面圖，且每個面的次數(shù)均為 3，則 G為極大平面圖 . 定理的應(yīng)用 上圖中，只有 (3)為極大平面圖 (1) (2) (3) School of Information Science and Engineering 極小非平面圖 定義： 若在非平面圖 G中任意刪除一條邊，所得圖 G?為平面圖，則稱 G為 極小非平面圖 . 由定義不難看出： (1) K5, K3,3都是極小非平面圖 (2) 極小非平面圖必為簡單圖 圖中所示各圖都是極小非平面圖 . School of Information Science and Engineering 定理 （歐拉公式的推廣）設(shè) G是具有 k（ k?2）個連通分支的平面圖，則 n?m+r=k+1 證明中對各連通分支用歐拉公式，并注意 即可 . ?? ???kii krr1)1( 歐拉公式 定理 設(shè) G為 n階 m條邊 r個面的連通平面圖，則 n?m+r=2 （此公式稱為 歐拉公式 ） 證 對邊數(shù) m做歸納法 m=0， G為平凡圖，結(jié)論為真 . 設(shè) m=k（ k?1）結(jié)論為真， m=k+1時分情況討論 . (1) G中無圈，則 G為樹，刪除一片樹葉，用歸納假設(shè) . (2) 否則，在某一個圈上刪除一條邊，進行討論 . School of Information Science and Engineering )2(2 ??? nl lm)2()d e g (21nmlrlRmrii ?????? ??)2(2 ??? nl lm)1(2 ???? knl lm解得 也可得： 定理 在具有 k（ k?2）個連通分支的平面圖中 ， 與歐拉公式有關(guān)的定理 定理 設(shè) G為連通的平面圖，且 deg(Ri)?l, l?3，則 證明：由定理 推論 K5, K3,3不是平面圖 . 63 ?? nm School of Information Science and Engineering 定理 設(shè) G為 n（ n?3）階 m條邊的簡單平面圖，則 m?3n?6. 證明：設(shè) G有 k（ k?1）個連通分支，若 G為樹或森林，當(dāng) n?3時， m?3n?6為真 . 否則 G中含圈，每個面至少由 l（ l?3）條邊圍成，又 2212 ???? lll定理 設(shè) G為 n（ n?3）階 m條邊的極大平面圖，則 m=3n?6. 證明：由定理 , 歐拉公式及定理 。 當(dāng) n?7 時，用反證法。 (1) (2) 子圖 (1) (2) School of Information Science and Engi
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1