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