圖論基本概念ppt課件(編輯修改稿)

　

【文章內容簡介】 2l個 有向圖：圖中長度為 l（ l?3）的圈，定義意義下為 l個 ② 同構意義下：長度相同的圈均為 1個 試討論 l=3和 l=4的情況 24 通路與回路的長度 定理 在 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 的初級回路 . 25 圖的連通性 無向圖的連通性 (1) 頂點之間的連通關系： G=V,E為無向圖 ① 若 vi 與 vj 之間有通路，則 vi?vj ② ?是 V上的等價關系 R={u,v| u,v ?V且 u?v} (2) G的連通性與連通分支 ① 若 ?u,v?V， u?v，則稱 G連通 ② V/R={V1,V2,…, Vk}，稱 G[V1], G[V2], …, G[Vk]為 連通分 支 ，其個數 p(G)=k (k?1)； k=1， G連通 26 短程線與距離 (3) 短程線與距離 ① u與 v之間的 短程線 ： u?v， u與 v之間長度最短的通路 ② u與 v之間的 距離 ： d(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) 27 無向圖的連通度 1. 刪除頂點及刪除邊 G?v —— 從 G中將 v及關聯的邊去掉 G?V?—— 從 G中刪除 V?中所有的頂點 G?e —— 將 e從 G中去掉 G?E?—— 刪除 E?中所有邊 2. 點割集與邊割集 點割集與割點 定義 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}為邊割集 28 點割集與割點 例 3 {v1,v4}， {v6}是點 割集， v6是割點 . {v2,v5} 是點割集嗎？ {e1,e2}， {e1,e3,e5,e6}， {e8}等是邊割集， e8是 橋， {e7,e9,e5,e6} 是邊割 集嗎？ 幾點說明： ? Kn中無點割集， Nn中既無點割集，也無邊割集，其中 Nn為 n 階零圖 . ? 若 G 連通， E?為邊割集，則 p(G?E?)=2， V?為點割集，則 p(G?V?)?2 29 點連通度與邊連通度 定義 G為連通非完全圖 點連通度 — ?(G) = min{ |V ?|?V ?為點割集 } 規定 ?(Kn) = n?1 若 G非連通， ?(G) = 0 若 ?(G)?k，則稱 G為 k連通圖 定義 設 G為連通圖 邊連通度 —— ?(G) = min{|E?|?E?為邊割集 } 若 G非連通，則 ?(G) = 0 若 ?(G)?r，則稱 G是 r 邊 連通圖 圖中， ?=?=1，它是 1連通圖 和 1邊 連通圖 30 幾點說明 ? ?(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) 請畫出一個 ???的無向簡單圖 31 有向圖的連通性 定義 D=V,E為有向圖 vi ? vj（ vi 可達 vj） —— vi 到 vj 有通路 vi ? vj（ vi 與 vj 相互可達） 性質 ? 具有自反性 (vi ? vi)、傳遞性 ? 具有自反性、對稱性、傳遞性 vi 到 vj 的短程線與距離 類似于無向圖中，只需注意距離表示法的不同 (無向圖中 d(vi,vj)，有向圖中 dvi,vj) 及 dvi,vj無對稱性 32 有向圖的連通性及分類 定義 D=V,E為有向圖 D弱連通 (連通 )—— 基圖為無向連通圖 D單向連通 —— ?vi,vj?V， vi?vj 或 vj?vi D強連通 —— ?vi,vj?V， vi?vj 易知，強連通 ?單向連通 ?弱連通 判別法 定理 D強連通當且僅當 D中存在經過每個頂點至少一次 的回路 定理 D單向連通當且僅當 D中存在經過每個頂點至少一 次的通路 33 擴大路徑法 無向圖中 設 G=V,E為 n 階無向圖， E??. 設 ?l 為 G中一條路徑，若 此路徑的始點或終點與通路外的頂點相鄰，就將它們擴到通 路中來，繼續這一過程，直到最后得到的通路的兩個端點不