Graph III

Size: px

Start display at page:

Download "Graph III"

谘紊舌哈
4 years ago
Views:

1 GRAPH Michael Tsai 20//2

2 2 Biconnected Components 相關名詞 Articulation point: 如果在 connected graph G 中的的一個 vertex v 被移除以後 ( 包含 v 和所有 incident 在它上面的 edge), 新的 graph G 會變成有兩塊以上的 connected components ( 複習 : 什麼是 connected components) Biconnected graph: 沒有 articulation point 的 graph Biconnected component: maximal biconnected subgraph 這邊 maximal 是說, 沒有一個可以包含它的 subgraph 是 biconnected 的

3 例子 Biconnected components: 猜一猜哪邊是 articulation point? ( 有沒有 articulation point?) 加了什麼邊可以讓它變成不是 articulation point?

4 4 例子 : 資訊系館網路各樓層研討室 cisco 2960 cisco 70 G 網路線實驗室 2 機房 cisco 2960 G 光纖 NTU CC Where is the articulation point(s)? How do we eliminate them? PC PC PC

5 DFS 另一用途可以用來尋找 articulation point & biconnected components 怎麼用呢? 首先先把 graph 做一次 dfs, 並標上 discover 的順序從哪個 vertex 開始不重要, edge 順序也不重要 ( 真的嗎? 自己驗證看看 )

6 6 尋找 articulation point 如果是 root 的話 ( 開始做 dfs 的地方 ), 且有超過一個的 children 是 articulation point 如果不是 root: 4 0 當有一個以上的小孩, 無法沿著它自己的後代及一條 nontree edge (back edge) 到達它的祖先的時候, 則為 articulation point back edge: 一條 edge (u,v), u 是 v 的祖先或者 v 是 u 的祖先

7 7 尋找 articulation point 定義一些 function 來找 articulation point low(u)=min{u.d, min{low(w) w is a child of u}, min{w.d (u,w) is a back edge}}

8 8 尋找 articulation point 當某 vertex v 有任何一個 child 的 low 值 >=v.d 時, 則 v 為 articulation point 4 0 low(u)=min{u.d, min{low(w) w is a child of u}, min{w.d (u,w) is a back edge}} v.d low

9 9 Minimum Cost Spanning Tree 電路設計需要把 N 個電子零件的接點連接在一起這些接點在不同的位置要如何把它們通通連接起來呢? 需要有 N- 條電線, 每一條把兩個接點連接起來怎麼樣才能使用最短的電線呢? 轉換 : G=(V,E) 是 undirected graph, V 是接點, E 所有可能的電線每一個 E (u,v) 的 weight w(u,v) 代表所需使用的電線長度須找出一個 acyclic 的 subset T E 連接所有的 vertex, 且使 w T = w(u, v) u,v T

10 0 Minimum Cost Spanning Tree T: acyclic 且連接所有 vertex, 所以為一棵 tree 且 span 到整個 graph, 所以稱為 spanning tree. 複習 : Spanning tree 須滿足那些條件?. 因為是 tree, 所以沒有 cycle 2. 因為是 tree, 所以正好有 n- 個 edge 下面介紹三種使用 greedy algorithm 產生 minimum cost spanning tree 的方法

11 一般型 Minimum Spanning Tree 演算法 GENERIC-MST(G,w) while A does not form a spanning tree find an edge (u,v) that is safe for A A=A * u, v + return A A 是最終的 MST 的 edge 的 subset 隨時 A 都保持 acyclic 隨時 G A = (V, A) 都是一個 forest 每次都選一個 edge, 把 G A 中兩棵 tree 連接起來 ( 因為不能出現 cycle) 最後共選 V - 條邊下面三個 algorithm 的前兩個都是用這個方法 Reading Assignment: 課本 2.

12 2 Kruskal s algorithm 這個方法是我覺得最直觀的方法. MST-KRUSKAL(G,w) A={} for each vertex v G. V MAKE-SET(v) sort G.E by w for each edge (u,v) G. E if FIND-SET(u) FIND-SET(v) A=A {(u,v)} UNION(u,v) return A 管理 set 的一些工具 function: MAKE-SET(v): 創造一個 set FIND-SET(v): 找到這個 set 的頭頭 (id) UNION(u,v): 把兩個 set 合併起來

13 Kruskal s algorithm MST-KRUSKAL(G,w) A={} for each vertex v G. V MAKE-SET(v) sort G.E by w for each edge (u,v) G. E return A O(Eα V ) if FIND-SET(u) FIND-SET(v) A=A {(u,v)} UNION(u,v) V 次 O(E log E) O(E) 次 α V = O log V = O(log E) E < V 2, 所以 log E = O(log V ) 管理 set 的資料結構相關內容請見課本 2 章管理 set 的一些工具 function: MAKE-SET(v), FIND-SET(v), & UNION(u,v) 執行共 m 個 operation 的時候 (n 個 item) 則執行時間為 O mα n O(E) 次 O( V + E α(v)) E V since G is connected O E log V

14 4 證明題證明 Kruskal s algorithm 會產生出 minimum cost spanning tree. () 證明當某 graph 有 spanning tree 的時候, Kruskal s algorithm 會產生出 spanning tree. (2) 證明這個產生出來的 spanning tree 一定是 cost 最小的. 證明 (): 什麼時候某 graph 一定有 spanning tree 呢? 原本是 connected 的 Algorithm 什麼時候會停下來呢? () 當 T 裡面已經有 n- 個 edge 了, 且正好每個 edge 都處理完畢 ( 成功, 不管它 ) (2) T 裡面還沒有 n- 個 edge, 但是每個 edge 都處理完畢, 而有些 node 沒有連接到 ( 我們的 algorithm 會不會造成這樣的情形呢?) 但是我們的程式只會把造成 cycle 的 edge 丟掉, 當把造成 cycle 的 edge 丟掉的時候, 不會因此讓某個 node 在 T 裡面沒有跟其他 vertex connected. 所以不會造成 (2) 的情形

15 證明題證明 (2) 假設 T 是用我們的 algorithm 做出來的 spanning tree 假設 U 是某一個 minimum cost spanning tree ( 可能有很多個, 其中一個 ) 既然都是 spanning tree, T 和 U 都有 n- 個 edge 有兩種情形 : () T 和 U 一模一樣, 則 T 就是 minimum cost spanning tree ( 沒什麼好證的 ) (2)T 和 U 不一樣. 則我們假設它們有 k 條 edge 不一樣, k 0.

16 6 證明題每次我們從 T 取出 k 條不一樣的 edge 中其中一條 ( 此 edge 不在 U 中 ), 從 cost 最小的開始到 cost 最大的. 把這條 edge( 我們叫它 t) 加入 U 的時候, 會產生一個 cycle 在 U 中這個 cycle 裡面, 一定有某一條 edge 不在 T 裡面, 我們叫它 u ( 因為 T 沒有 cycle). 我們把 u 從 U 拿掉, 這個新的 spanning tree 叫做 V V 的 total cost 就是 cost(u)-cost(u)+cost(t). T U V t k 條不在 U 中的, 其中最小的為 t u

17 7 證明題但是 cost(t) 不能小於 cost(u), 否則 V 就比 U 的 cost 少了 (contradiction) cost(t) 也不能大於 cost(u), 不然當初我們做 T 的時候, 應該會先選到 u, 但是因為它會造成 cycle 所以才不選它. 所以 u 和所有在 T 裡面 cost 跟 cost(u) 一樣大或者更小的 edge 會造成 cycle. 但是剛剛既然我們先選到 t ( 在 T 裡面不在 U 裡面最小的一個 ), 表示這些 cost 跟 cost(u) 一樣大或者更小的 edge 都在 U 裡面表示 u 和這些 edge 都在 U 裡面, U 會有 cycle (contradiction)

18 8 證明題搞了半天, 目前可以證明 cost(f)=cost(e) 所以 cost(v)=cost(u) 重複以上步驟, 可以最後變成 V=T 且 cost(v)=cost(t)=cost(u) 所以 T 也是 minimum cost spanning tree

19 9 Prim s Algorithm u.key: 記錄到 G A 最短的邊的 weight u.pi: 紀錄上面講的那條邊的另外一端是哪個 vertex MST-PRIM(G,w,r) for each u G. V u.key= u.pi=nil r.key=0 Q=G.V while Q {} u=extract-min(q) for each v G.Adj[u] if v Q and w(u,v)<v.key v.pi=u v.key=w(u,v) A={(v,v.pi):v V-{r}}

20 20 Sollin s algorithm 一開始每個 vertex 自己是一個 forest 保持都是 forest 每個 stage, 每個 forest 都選擇一個該 forest 連到其他 forest 的 edge 中 cost 最小的一個執行到沒有 edge 可以選了, 或者是變成 tree 了

21 2 Shortest paths 目標 : 找出 vertex u 到 graph G 中任何一點的最短距離 TO VERTEX PATH LENGTH No path

22 22 Dijkstra s algorithm Set S 裡面有一些已經加入的 vertex ( 包括起始點 v 0 ) w 不在 S 中, 則有 distance[w] 紀錄從 v 0 經過 S 中的任意個 vertex 後, 最後到達 w 的這樣形式的最短路徑 S v 0 w

23 2 Dijkstra s algorithm 每次選擇 u, 為 distance[u] 中最小的選進 S 以後, v 0 到 u 的 shortest path 就找到了所以找到 shortest path 的順序會是由最短的找到最長的把 u 選進去 S 以後, 就要把所有 u 的 edge <u,w> 都看一遍 : if distance[w]>distance[u]+cost(<u,w>) distance[w]=distance[u]+cost(<u,w>)

24 24 小證明如果下一個選擇的 vertex 為 u, 為什麼 v 0 到 u 的最短 path 會正好是前面的 vertex 都在 S 中, 只有 u 不在 S 中呢? 因為假如有 path 中有 vertex w 也不在 S 中, 那麼表示 path 中會有一段是 v 0 到 w, 而且長度比較短 ( 因為是 sub path) 可是這樣的話, 應該 w 之前應該就要被選過了 ( 應該要在 S 中 ) (contradiction) 所以 v 0 到 u 的最短 path 前面的 vertex 都在 S 中, 只有 u 不在 S 中

25 2 例子 selection Initial

26 26 例子 selection Initial

27 27 更多動畫例子 Time complexity? 答案 : O( V 2 ) 每次都要看一次 distance[], 共 n 個

因為假如有 path 中有 vertex w 也不在 S 中, 那麼表示 path 中會有一段是 v 0 到 w, 而且長度比較短 ( 因為是 sub path) 可是這樣的話, 應該 w

28 28 Bellman-Ford algorithm 另外一種找到 shortest path 的 algorithm 可以 handle path cost 是負的情形為什麼 Dijkastra 有問題? 如果下一個選擇的 vertex 為 u, 為什麼 v 0 到 u 的最短 path 會正好是前面的 vertex 都在 S 中, 只有 u 不在 S 中呢? 因為假如有 path 中有 vertex w 也不在 S 中, 那麼表示 path 中會有一段是 v 0 到 w, 而且長度比較短 ( 因為是 sub path) 可是這樣的話, 應該 w 之前應該就要被選過了 ( 應該要在 S 中 ) (contradiction) 所以 v 0 到 u 的最短 path 前面的 vertex 都在 S 中, 只有 u 不在 S 中假設 cost 可以是負的, 這就不一定正確了.

29 29 Bellman-Ford algorithm 定義 dist l u 為從 v 0 到 u 的最短路徑, 最多經過 l 條 edge 一開始 dist u 為 cost(<v 0,u>) ( 如果沒有 edge 則為無限大 ) 由 dist k,- 算 dist k,- 最後算到 dist n u 為最後 shortest path 解 ( 因為每個 node 最多走一遍, 不然就有 cycle 了 )

30 0 Bellman-Ford algorithm 由 dist k,- 算 dist k,- 怎麼算呢? 有以下兩種可能性 : 如果從 v 0 到 u 的使用最多 k 個 edge 的最短路徑其實使用了 k- 或更少 edge 的話, 則 dist k u = dist k u 如果從 v 0 到 u 的使用最多 k 個 edge 的最短路徑使用了 k 條 edge 的話, 則最短路徑可能為經過別的 vertex i 的 shortest path ( 用了最多 k- 條 edges) 後再走 edge <i,u>. 綜合以上兩條規則 : dist k u = min *dist k u, min i dist k i + cost i, u +

31 例子 vertex 0 到其他 vertices 的最短路徑 : k 其他例子 :

32 2 例子 k 其他例子 :

33 一些可以思考的東西 time complexity =? 答案 : adjacency matrix: O( V ) adjacency lists: O V E 前面都沒有提到怎麼真的輸出 path 本身經過哪些 vertex 想想看, 要怎麼做? 答案 : 每次 update distance 的時候, 順便 update 附在旁邊的 linked list. ( 用 linked list 表示 path)

34 TANET 4

35 Routing protocol 要計算從某個點到另外一個點的路徑 (route) 目標 : 連線速度? path cost =? Dijkstra 比較適合還是 Bellmanford 比較適合? 答案 : 似乎 Bellman-Ford 比較適合, 因為不需要知道所有 link cost 即可建立 routing table

36 周末愉快 6

Graph

Graph 連載 : 學生上課睡覺姿勢大全 http://www.wretch.cc/blog/chi771027/26489957 GRAPH 2 Michael Tsai 2013/4/23 2 Breadth-First Tree BFS 做出一棵樹 : Breadth-First Tree 這個樹其實也就是 BFS 產生出來的 predecessor subgraph of G: G π = V π,