離散數(shù)學(xué)耿素云第5版(編輯修改稿)
2025-02-12 20:25 本頁面
【文章內(nèi)容簡介】 ??(D)=3, ??(D)=1, ?(D)=5, ?(D)=3. 12 圖論基本定理 —— 握手定理 定理 任意無向圖和有向圖的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的 2倍 , 并且有向圖的所有頂點(diǎn)入度之和等于出度之和等于邊數(shù) . 證 G中每條邊（包括環(huán)）均有兩個(gè)端點(diǎn)，所以在計(jì)算 G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供 2度， m條邊共提供 2m度 . 有向圖的每條邊提供一個(gè)入度和一個(gè)出度 , 故所有頂點(diǎn)入度之和等于出度之和等于邊數(shù) . 推論 任意無向圖和有向圖的奇度頂點(diǎn)個(gè)數(shù)必為偶數(shù) . 13 圖的度數(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 14 握手定理的應(yīng)用 例 1 (3,3,3,4), (2,3,4,6,8)能成為圖的度數(shù)列嗎 ? 解 不可能 . 它們都有奇數(shù)個(gè)奇數(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 15 握手定理的應(yīng)用 (續(xù) ) 例 3 證明不存在具有奇數(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ù) . 這與握 手定理的推論矛
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1