離散數(shù)學(xué)課件圖論ppt課件(參考版)
2025-05-05 05:11本頁(yè)面
【正文】 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正則圖 . 。 School of Information Science and Engineering 第十七章 小結(jié) ? 主要內(nèi)容 ?平面圖的基本概念 ?歐拉公式 ?平面圖的判斷 ?平面圖的對(duì)偶圖 ? 基本要求 ?理解基本概念：平面圖、平面嵌入、面、次數(shù)、極大平面圖、極小非平面圖、對(duì)偶圖 ?牢記極大平面圖的主要性質(zhì)和判別方法 ?熟記歐拉公式及推廣，并能用歐拉公式及推廣形式證明有關(guān)定理與命題 ?會(huì)用庫(kù)拉圖斯基定理證明某些圖不是平面圖 ?記住平面圖與它的對(duì)偶圖階數(shù)、邊數(shù)、面數(shù)之間的關(guān)系 School of Information Science and Engineering 練習(xí) 1 解 設(shè) G的階數(shù)、邊數(shù)、面數(shù)分別為 n, m, r. (1) 否則，由歐拉公式得 2m 5r = 5 (2+m?n) ① 由于 ?(G)?3及握手定理又有 2m ? 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， ②
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1