離散數(shù)學課件圖論ppt課件-資料下載頁
2025-05-02 05:11本頁面
【正文】 ? 3n ② 由①與②得 m?30 ③ 又有 r=2+m?n 12 ④ 由④及②又可得 m30 ⑤ ③ ,⑤ 是矛盾的 . (2) 正十二面體是一個反例 1. 設 G是連通的簡單的平面圖，面數(shù) r12， ?(G)?3. (1) 證明 G中存在次數(shù) ?4的面 (2) 舉例說明當 r=12時， (1) 中結(jié)論不真 . School of Information Science and Engineering 2. 設 G是階數(shù) n?11的無向平面圖，證明 G和 不可能全是平面圖 . G證 只需證明 G和 中至少有一個是非平面圖 . 采用反證法 . 否則 與 G 都是平面圖，下面來推出矛盾 . G與 的邊數(shù) m, m?應滿足 ( Kn的邊數(shù) ) ① 由鴿巢原理知 m或 m?，不妨設 m， ② GGG2)1(39。 ??? nnmm4)1( ?? nnm又由定理 知 m ? 3n ? 6 ③ 由②與③得 n2?13n+24 ? 0 ④ 由④解得 2 ? n ?10 ⑤ ⑤ 與 n ?11矛盾 . 其實，當 n=9,10時，命題結(jié)論已真 . 練習 2 School of Information Science and Engineering 3. 證明下圖為非平面圖 練習 3 School of Information Science and Engineering 證明 證明：用庫拉圖斯基定理證明 下圖為原圖的子圖，它是 K3,3，由庫拉圖斯基定理得證。 School of Information Science and Engineering 圖 20 圖 19 練習 4 4. 設 G為 n（ n?3）階極大平面圖，證明 G的對偶圖 G*是 2邊連通的 3正則圖 . 證明：證明中用上 n?3的極大平面圖的性質(zhì)，以及平面圖與對偶圖的關(guān)系，對偶圖的連通性等 . (1) 證 G*是 2邊連通的 . 由 G*的連通性可知， ?(G*)?1，又因為 G為極大平面 圖，故 G為簡單圖，所以 G*中無橋（因為 G中無環(huán)）， 所以， ?(G*)?2. 故 G*為 2邊連通的 . (2) 證 G*是 3正則圖 . 易知 G*為簡單圖，且每個頂點的度數(shù)均為 3（由定理 ），故 G*為 3正則圖 .
教學課件相關(guān)推薦
鄂ICP備17016276號-1