第五章圖論graphtheory(編輯修改稿)
2025-08-28 13:14 本頁面
【文章內(nèi)容簡介】 d e g ?????? ?niinii vv由 G是競賽圖可知： 1)(d e g)(d e g ????? nvv ii))(( d e g))(( d e g11?????? ?niinii vv證明：等價于證明 而由有向圖頂點(diǎn)度數(shù)和定理可知： 36 競賽圖的性質(zhì)證明（續(xù)） 2112 ))(( d e g))(( d e g ?????? ?niinii vv)))(( d e g))(( ( d e g 212inii vv??? ?? ??????? ???niiiii vvvv1))(d e g)() ) ( ( d e g(d e g)(( ( d e g???? ???niii vvn1))(d e g)() ( ( d e g1(???? ???niii vvn1))(d e g)(( ( d e g)1()))(( d e g))(( ( d e g)(1(1 1? ?? ??? ???niniii vvn0)1( ??? n0?37 正則圖 (regular graph) ? 所有頂點(diǎn)的度 均相同 的 簡單圖 稱為 正則圖 。若頂點(diǎn)的度數(shù) k，則稱作 k正則圖 2正則圖 3正則圖 38 圖的操作 ? 刪邊 ? 刪去圖 G中的若干條邊，但仍保留被刪除邊的端點(diǎn) ? 刪點(diǎn) ? 刪去圖 G中的若干個頂點(diǎn)以及與被刪點(diǎn)所關(guān)聯(lián)的所有邊 39 圖的操作 刪邊 v2 v3 e2 e1 e3 e5 v4 v1 e4 v2 v3 e2 e3 e5 v4 v1 e4 刪 e1 40 圖的操作 刪點(diǎn) v2 v3 e2 e1 e3 e5 v4 v1 e4 v2 v3 e3 e5 v4 e4 刪 v1 41 子圖 ? 從圖 G中刪除若干條邊或頂點(diǎn)所得到的圖稱為 G的 子圖 。 v2 v3 e2 e1 e3 e5 v4 v1 e4 v2 v3 e2 e3 e5 v4 v1 e4 v2 v3 e3 e5 v4 e4 G G1 G2 42 ? 主子圖 ? 生成子圖 ? 邊集的導(dǎo)出子圖 ? 點(diǎn)集的導(dǎo)出子圖 子圖的類型 43 主子圖 ? 在圖 G中刪去 一個頂點(diǎn) 后所得的子圖稱為圖 G的主子圖 b a c d e G b c d e 44 生成子圖 ? 若 G’ 是 G的 子圖， 且 G’含有 G的所有頂點(diǎn) ，則稱 G’是 G的生成子圖 b a c d e G b a c d e G’ 45 邊集的導(dǎo)出子圖 ? 設(shè) E’是 E(G)的 非空子集 ，則 以 E’為邊集，以E’中邊的端點(diǎn)全體為頂點(diǎn)集 所構(gòu)成的圖稱為G的由邊集 E’導(dǎo)出的子圖。 ? 記為 G[E’]。 46 邊集的導(dǎo)出子圖示例 ? 邊集 E’={(a,b),(b,e),(a,e),(a,c)} 的導(dǎo)出子圖 b a c e b a c d e G G[E’] 47 點(diǎn)集的導(dǎo)出子圖 ? 設(shè) V’是 V(G)的 非空子集 ，則以 V’為頂點(diǎn)集 ，以 G中兩端點(diǎn)均在 V’中的邊的全體為邊集 ，所構(gòu)成的子圖稱為 G的由 V’導(dǎo)出的子圖。 ? 記為 G[V’] 48 點(diǎn)集的導(dǎo)出的子圖示例 ? 點(diǎn)集 V’={a,b,c,e}導(dǎo)出的子圖 b a c e d G G[V’] 49 回顧 子圖類型 特點(diǎn) 主子圖 生成子圖 邊集 E‘導(dǎo)出子圖 點(diǎn)集 V’的導(dǎo)出子圖 原圖刪除一個頂點(diǎn) 包含原圖所有頂點(diǎn) 由邊集 E’及 E’關(guān)聯(lián)的頂點(diǎn)構(gòu)成 由頂點(diǎn)集 V’以及端點(diǎn)都在 V’中的邊構(gòu)成 50 練習(xí) (1) ? 請判斷下列哪些圖是圖 G的生成子圖： A B C D G 回答 ： C和 D 51 練習(xí) (2) ? 請判斷下列哪個圖是圖 G的由邊集 E’＝ {e1,e2,e6,e7}的導(dǎo)出子圖： A B C D
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1