離散數(shù)學(xué)61圖的基本概念(編輯修改稿)
2025-02-12 20:21 本頁面
【文章內(nèi)容簡(jiǎn)介】 證 每條邊恰好提供 1個(gè)入度和 1個(gè)出度 11 圖的度數(shù)列 設(shè)無向圖 G的頂點(diǎn)集 V={v1, v2, … , vn} G的度數(shù)列 : d(v1), d(v2), … , d(vn) 如右圖度數(shù)列 :4,4,2,1,3 設(shè)有向圖 D的頂點(diǎn)集 V={v1, v2, … , vn} D的度數(shù)列 : d(v1), d(v2), … , d(vn) D的出度列 : d+(v1), d+(v2), … , d+(vn) D的入度列 : d?(v1), d?(v2), … , d?(vn) 如右圖度數(shù)列 :5,3,3,3 出度列 :4,0,2,1 入度列 :1,3,1,2 e1 e2 e3 e4 e5 e6 e7 v5 v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 d a b c 12 實(shí)例 (2) 能 例 1 下述 2組數(shù)能成為無向圖的度數(shù)列嗎 ? (1) 3,3,3,4。 (2) 1,2,2,3 解 (1) 不可能 . 有奇數(shù)個(gè)奇數(shù) . 13 實(shí)例 例 2 已知圖 G有 10條邊 , 4個(gè) 3度頂點(diǎn) , 其余頂點(diǎn)的度數(shù)均小 于等于 2, 問 G至少有多少個(gè)頂點(diǎn) ? 解 設(shè) G有 n個(gè)頂點(diǎn) . 由握手定理 , 4?3+2?(n4)?2?10 解得 n?8 例 3 已知 5階有向圖的度數(shù)列和出度列分別為 3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 14 實(shí)例 例 4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的 多面體 . 證 用反證法 . 假設(shè)存在這樣的多面體 , 作無向圖 G=V,E, 其中 V={v | v為多面體的面 }, E={(u,v) | u,v?V ? u與 v有公共的棱 ? u?v}. 根據(jù)假設(shè) , |V|為奇數(shù)且 ?v?V, d(v)為奇數(shù) . 這與握手定理的推論矛盾 . 15 實(shí)例 例 5 設(shè) 9階無向圖的每個(gè)頂點(diǎn)的度數(shù)為 5或 6, 證明它至少有 5個(gè) 6度頂點(diǎn)或者至少有 6個(gè) 5度頂點(diǎn) . 證 討論所有可能的情況 . 設(shè)有 a個(gè) 5度頂點(diǎn)和 b個(gè) 6度頂點(diǎn) (1)a=0, b=9。 (2)a=2, b=7。 (3)a=4, b=5。 (4)a=6, b=3。 (5)a=8, b=1 (1)~(3) 至少 5個(gè) 6度頂點(diǎn) , (
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1