Chapter 4 Spanning Trees

Presentation on theme: "Chapter 4 Spanning Trees"— Presentation transcript:

1 Chapter 4 Spanning Trees
Graph Theory Chapter 4 Spanning Trees 大葉大學 資訊工程系 黃鈴玲

2 Contents 4.1 Spanning Trees and Forests
4.3 The Adjacency Matrix of a Graph 4.4 The Incidence Matrix of a Graph 4.7 Minimum Cost Spanning Trees

3 4.1 Spanning Trees and Forests
Definition 4.1 spanning tree spanning forest

4 4.3 The Adjacency Matrix of a Graph
Definition 4.9 A(G): nn 矩陣 (n為點數) aij代表點ui與uj間連接的邊數

5 Example 4.10 無向圖時，A(G)為對稱矩陣 一條邊對應到矩陣的兩個1

6 Theorem 4.16 Let G be a graph on the n vertices labeled as V(G) ={u1, u2, …, un}. The entry aij(k) in A(G)k is the number of distinct walks from ui to uj of length k in G. Exercise: 計算下圖的A(G)2及A(G)3，u3與u4間有幾條長度為3的 walk? 請列舉出來。

7 4.4 The Incidence Matrix of a Graph
e1 e2 e3 e4 e5 e6 u1 u2 u3 u4 u5 紀錄「點」與「邊」的關係

8 4.7 Minimum Cost Spanning Trees
Definition 4.36

9 Definition 4.37

10 Example 每一步挑選weight最小且加入後不形成cycle的邊 T1= T3 T2 y x w u v 2 5 4 3 1 6 G

11 y x w u v 2 5 4 3 1 6 G T4 y x w u v 1 2 T5 y x w u v 1 2 3

12

13 Example 挑選與現有的Tree相連且weight最小的邊，加入Tree中 T1 T3 T2 2 y x w u v 2 5 4 3 1
6 G 挑選與現有的Tree相連且weight最小的邊，加入Tree中 T1 T3 u w u v 1 2 T2 u v 1

14 y x w u v 2 5 4 3 1 6 G T4 T5 y x w u v 1 3 2 x w u v 1 2 3

15 Exercise: For the following graph, find minimum spanning trees by Kruskal’s algorithm and Prim’s algorithm. a b x z y c u v w 5 6 9 8 7 4 3 2 1