離散數(shù)學課件圖論(2)(編輯修改稿)
2025-02-12 20:45 本頁面
【文章內容簡介】 通路與回路 [定理 ] 在 n 階圖 G中，若從頂點 vi 到 vj（ vi?vj）存在通路，則從 vi 到 vj 存在長度小于或等于 n?1 的通路 . [推論 ] 在 n 階圖 G中，若從頂點 vi 到 vj（ vi?vj）存在通路，則 從 vi 到 vj 存在長度小于或等于 n?1的初級通路（路徑） . [定理 ] 在一個 n 階圖 G中，若存在 vi 到自身的回路，則一定存在 vi 到自身長度小于或等于 n 的回路 . [推論 ] 在一個 n 階圖 G中，若存在 vi 到自身的簡單回路，則一 定存在長度小于或等于 n 的初級回路 . ? vs1 ? vi+1 ? ? vt+1 ? vs = vt ? vs+1 vi ? vt1 ? ? vj ? vj1 …... ….. School of Information Science and Engineering 143 圖的連通性 1. 無向圖的連通性 ［兩個結點連通］ 在無向圖中，結點 u和 v之間如果存在一條通 路 ， 則稱 u與 v是連通的 。記作 u?v 規(guī)定 : 對任何結點 u， u?u。 ［結點之間的連通關系是個等價關系］ 令 G=V, E是無向圖， R是 V上連通關系，即 R={u,v| u,v ?V且 u?v} 顯然 R具有自反、對稱和傳遞性。 于是可以求商集 V/R。 ch gbadef例 ： 給定右圖所示 V/R={ {a,b,g}， {c,d,e,f}， {h} } School of Information Science and Engineering 143 圖的連通性 ［ G的連通性與連通分支 ］ ① 若 ?u, v?V， u?v，則稱 G是連通的 ② V/R={V1,V2,…, Vk}，稱 等價類構成的子圖 G[V1], G[V2], …, G[Vk]為 G的連通分支 ，其個數(shù) p(G)=k (k?1)； k=1， G是連通的。 下面實例中 p(G1)=3 p(G2)=2 p(G3)=1 ch gbadef123456a bcdG1G2G3 School of Information Science and Engineering 143 圖的連通性 ［距離］ ① u與 v之間的 距離 ： d(u,v)— u與 v之間長度最短的通路。 ② d(u,v)的性質： d(u,v)?0, u?v時 d(u,v)=? d(u,v)=d(v,u) d(u,v)+d(v,w)?d(u,w) [刪除頂點及刪除邊 ] G?v —— 從 G中將 v及關聯(lián)的邊去掉 G?V?—— 從 G中刪除 V?中所有的頂點 G?e —— 將 e從 G中去掉 G?E?—— 刪除 E?中所有邊 School of Information Science and Engineering 143 圖的連通性 ［ 點割集與邊割集 ］ 定義： G=V,E, V??V V?為 點割集 —— p(G?V?)p(G)且有極小性 v為 割點 —— {v}為點割集 定義： G=V,E, E??E E?是 邊割集 —— p(G?E?)p(G)且有極小性 e是 割邊 （橋） —— {e}為邊割集 ? 上例中 {v2,v5}是點割集嗎？ {e7,e9,e5,e6} 是邊割集嗎？ 例： {v1,v4}， {v6}是點割集，v6是割點。 {e1,e2}， {e1,e3,e5,e6}， {e8}等是邊割集， e8是橋。 School of Information Science and Engineering 143 圖的連通性 ［ 說明 ］ ? Kn中無點割集， Nn中既無點割集，也無邊割集，其中 Nn為 n 階零圖 . ? 若 G 連通， E?為邊割集，則 p(G?E?)=2， V?為點割集，則 p(G?V?)?2 [點連通度 ]— G為連通非完全圖， ?(G) = min{ |V ?|?V ?為點割集 } 規(guī)定 ?(Kn) = n?1 若 G非連通， ?(G) = 0。 若 ?(G)?k，則稱 G為 k連通圖 [邊連通度 ]— G為連通圖， ?(G) = min{|E?|?E?為邊割集 } 若 G非連通，則 ?(G) = 0 若 ?(G)?r，則稱 G是 r 邊連通圖 問題： 求上例中的點連通度和邊連通度。 School of Information Science and Engineering 143 圖的連通性 ［ 說明 ］ ? ?(Kn)=?(Kn)=n?1 ? G非連通，則 ?=?=0 ? 若 G中有割點，則 ?=1，若有橋，則 ?=1 ? 若 ?(G)=k, 則 G是 1連通圖， 2連通圖， … ， k連通圖，但不是 (k+s)連通圖， s?1 ? 若 ?(G)=r, 則 G是 1邊連通圖， 2邊連通圖， … ， r邊連通圖，但不是 (r+s)邊連通圖， s?1 ? ?, ?, ?之間的關系 . [定理 ] ?(G)??(G)??(G) 問題： 請畫出一個 ???的無向簡單圖。 School of Information Science and Engineering 143 圖的連通性 2. 有向圖的連通性 [定義 ] D=V,E為有向圖 vi ? vj（ vi 可達 vj） —— vi 到 vj 有通路 vi ? vj（ vi 與 vj 相互可達） [性質 ] ? 具有自反性 (vi ? vi)、傳遞性 ? 具有自反性、對稱性、傳遞性 [vi 到 vj 的距離 ] 類似于無向圖中，只需注意距離表示法的不同 (無向圖中 d(vi,vj)，有向圖中 dvi,vj) 及 dvi,vj無對稱性 School of Information Science and Engineering 143 圖的連通性
規(guī)章制度相關推薦
鄂ICP備17016276號-1