Graph Theory Graph theory is the study of the properties of graph structures. It provides us with a language with which to talk about graphs.

Presentation on theme: "Graph Theory Graph theory is the study of the properties of graph structures. It provides us with a language with which to talk about graphs."— Presentation transcript:

1 Graph Theory Graph theory is the study of the properties of graph structures. It provides us with a language with which to talk about graphs.

2 Degree The degree of a vertex is the number of edges incident upon it.
The sum of the vertex degrees in any undirected graph is even (twice the number of edges). Every graph contains an even number of odd-degree vertices.

3 Connectivity A graph is connected if there is an undirected path between every pair of vertices. The existence of a spanning tree is sufficient to prove connectivity. The vertex (edge) connectivity is the smallest number of vertices (edges) which must be deleted to disconnect the graph.

4 Some terms articulation vertex  biconnected
bridge  edge-biconnected Testing for articulation vertices or bridges is easy via brute force.

5 Cycles Eulerian cycle (path): a tour which visits every edge of the graph exactly once. Actually, it is a circuit, not a cycle, because it may visit vertices more than once. A mailman’s route is ideally an Eulerian cycle, so he can visit every street (edge) in the neighborhood once before returning home.

6 Eulerian Circuit

7 An undirected graph contains an Eulerian cycle if it is connected and every vertex is of even degree. A Hamiltonian cycle is a tour which visits every vertex of the graph exactly once. The traveling salesman problem asks for the shortest such tour on a weighted graph.

8 TSP

9 Planer Graph Euler’s formula: n-m+f=2 n:# of vertices m:# of edges
f: # of faces Trees: m=n-1, f=1 Cubes: n=8, m=12, f=6

10 MST Kruskal’s algorithm: starting from a minimal edge
Prim’s algorithm: starting from a given vertex How about maximum spanning tree and Minimum Product spanning tree

11 Kruskal’s Algorithm Algorithm Kruskal(G)
Input：G=(V, E)為無向加權圖(undirected weighted graph)，其中V={v0,…,vn-1} Output：G的最小含括樹(minimum spanning tree, MST) T← //T為MST，一開始設為空集合 while T包含少於n-1個邊 do 選出邊(u, v)，其中(u, v)E，且(u, v)的加權(weight)最小 E←E-(u, v) if ( (u, v)加入T中形成循環(cycle) ) then 將(u, v)丟棄 else T←T(u, v) return T

12 Kruskal’s Algorithm -Construct MST

13 Prim’s algorithm Algorithm Prim(G)
Input：G=(V, E)為無向加權圖(undirected weighted graph)，其中V={v0,…,vn-1} Output：G的最小含括樹(minimum spanning tree, MST) T← //T為MST，一開始設為空集合 X←{vx} //隨意選擇一個頂點vx加入集合X中 while T包含少於n-1個邊 do 選出(u, v)E，其中uX且vV-X，且(u, v)的加權(weight)最小 T←T(u, v) X←X{v} return T

14

15

16 One-to-all shorted path
Dijkstra演算法: Dijkstra演算法屬於求取單一來源(source)至所有目標(destination)頂點的一至多(one-to-all)最短路徑演算法

17 圖的最短路徑 我們將d[u]以加中括號的方式標記在每一個頂點旁，使用圖8-5來說明Dijkstra演算法求頂點A到每一個頂點最短路徑的過程。
若要讓Dijkstra演算法也能夠求出每一條最短路徑所經過的每一個頂點，則我們要將每一頂點在最短路徑中的前一頂點紀錄下來，其作法為增加一個陣列p(代表predecessor，前行者)來記錄最短路徑中的每一個頂點的前一頂點。並將Dijkstra演算法之if敘述修改如下： if (d[u]+w[u][x]<d[x]) then d[x]←d[u]+w[u][x] p[x]←u //此敘述為新加入者，代表在最短路徑中頂點ｘ的前一頂點為ｕ

18 圖8-5

19 圖8-5

20 圖的最短路徑 以下我們以表8-1來說明Dijkstra演算法的執行過程：

21 All-pair shortest path
Floyd-Warshall的所有頂點對最短路徑(all-pair shortest path)演算法：

22 圖的最短路徑 以下我們在圖8-6中使用圖8-5中的圖(graph)來說明Floyd-Warshall的所有頂點對最短路徑演算法執行過程，請注意，我們使用代表在啟始狀況之值，代表在迴圈第一次，第二次，…，及第k次執行時陣列c的值。

23 圖8-6

24 圖8-6