離散數(shù)學(xué)第十七章平面-資料下載頁(yè)
2025-01-16 20:38本頁(yè)面
【正文】 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é)論不真 . 25 2. 設(shè) G是階數(shù) n?11的無(wú)向平面圖，證明 G和 不可能全是平面圖 . G證 只需證明 G和 中至少有一個(gè)是非平面圖 . 采用反證法 . 否則 與 G 都是平面圖，下面來(lái)推出矛盾 . G與 的邊數(shù) m, m?應(yīng)滿(mǎn)足 ( 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 26 3. 證明下圖為非平面圖 練習(xí) 3 27 證明 證 用庫(kù)拉圖斯基定理證明 方法一 . 下圖為原圖的子 圖，它是 K3,3，由庫(kù)拉圖斯 基定理得證命題 . 方法二 . 下圖為原圖的子圖（刪除邊 (a,f)），收縮本圖中的 (a,e)和 (f,g)所得圖為 K5, 由庫(kù)拉圖斯基定理得證命題 . 28 圖 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正則圖 .
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1