離散數(shù)學(xué)第8章圖論8樹-資料下載頁
2025-01-16 20:15本頁面
【正文】 立 : nkmk+dk = 2 。當(dāng) m=k+1時，考慮刪除一條邊后仍然連通的情況。 (1) 如果 G有回路，則刪除回路上一條邊后的圖邊數(shù)減少一，面數(shù)減少一，故公式對 G成立： nk(mk+1)+(dk+1) = 2. (2) G沒有回路，只有割邊，必有度數(shù)為一的結(jié)點，刪除相應(yīng)割邊的一度頂點后，結(jié)點數(shù)和邊數(shù)分別減少一，面數(shù)不變，故仍然有 ( nk +1)(mk+1)+dk = 2. ? 歐拉公式對非簡單圖仍然成立。 37 返回 結(jié)束 歐拉公式 ? 對于 n個頂點， m條棱， d個面的凸多面體，nm+d=2. [推論 ] 設(shè)平面圖 G的連通分支數(shù)為 k，并有 n個頂點， m條邊， d個域，則有 nm+d = k+1。 [證明 ] 對每個連通分支使用歐拉公式，注意它們共同擁有一個無窮面。 [定理 ] 若圖 G是簡單的平面圖，則圖 G至少有一個頂點的度 小于 6。 38 返回 結(jié)束 極大平面圖 [極大平面圖 ] 設(shè) G=(V,E)為簡單平面圖， |V|?3，若對任意 vi ,vj?V，且 (vi ,vj) ? E，有 G?=(V, E?{(vi ,vj)})為非平面圖，則稱 G為一個極大平面圖。 ? “極大性”乃針對固定頂點數(shù)的圖的邊的數(shù)目而言。 39 返回 結(jié)束 極大平面圖 ? [極大平面圖的性質(zhì) ] ? 極大平面圖是連通圖。 ? 極大平面圖的每個面都由 3條邊組成。 ? 極大平面圖有 3d=2m（ d為面數(shù)目， m 為邊數(shù)目）。 [定理 ] 設(shè)極大平面圖 G有 n個頂點， m條邊， d個域，則有 m=3n6， d=2n4。 [證明 ] 將 3d=2m代入歐拉公式。 [推論 ] 簡單平面圖 G有 m? 3n6， d ? 2n4。 [定理 ] 簡單平面圖至少有一個頂點的度小于 6。 [證明 ] 設(shè)任一點的度 ? 6，得 m? 3n，矛盾。 40 返回 結(jié)束 非平面圖 [例 ] K3,3 K5 K3,3 K5 是不可平面的。 [證明 ] 如果 G是平面圖，則有 m?3n6, 將n=5,m=10代入得到 10?9,矛盾！ K3,3 是不可平面的。 [證明 ] 注意 K3,3中的回路長度是偶數(shù)，至少是 4， 即每個面的度數(shù)至少是 4。所以， 4|R|?2|E|. 如果K3,3 是可平面的，則面數(shù)= 5， 由此的 20?18。矛盾！ 41 返回 結(jié)束 非平面圖 ? K5 和 K3,3 稱為基本的不可平面圖，或 Kuratowski (庫拉圖斯基 )圖。 [同胚 ] 設(shè) G是一個平面圖，通過刪除 G的一條邊 (x,y)，并且添加一個新結(jié)點 a和兩條邊 (x,a)與 (a,y)(所獲得的任何圖也是平面圖 )，這樣的操作成為初等細(xì)分。若可以從相同的圖 G通過一系列初等細(xì)分來獲得圖 G1和 G2，稱 G1和 G2是同胚的 (homeomorphism)。 例 ：兩個同胚圖 42 返回 結(jié)束 非平面圖 ? 與 K5同胚的圖，稱為 K(1)型圖；與 K3,3同胚的圖，稱為K(2)型圖； ? K(1)型圖和 K(2)型圖統(tǒng)稱 K型圖。 ? Kuratowski 定理 圖 G=(V,E) 可平面當(dāng)且僅當(dāng) G中不存在任何 K型子圖。 庫拉圖斯基定理給出了平面圖的充要條件，但用它并不能得出判別一個圖是否為平面圖的有效算法。 ? 根據(jù) Kuratowski定理，可以斷定：所有 樹 都是平面圖。 43 返回 結(jié)束 非平面圖 ? [例 ]彼得森 (petersen) 圖不是平面圖
高考資料相關(guān)推薦
鄂ICP備17016276號-1