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