Chapter 4 Spanning Trees Graph Theory Chapter 4 Spanning Trees 大葉大學 資訊工程系 黃鈴玲 2011.11
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
4.1 Spanning Trees and Forests Definition 4.1 spanning tree spanning forest
4.3 The Adjacency Matrix of a Graph Definition 4.9 A(G): nn 矩陣 (n為點數) aij代表點ui與uj間連接的邊數
Example 4.10 無向圖時，A(G)為對稱矩陣 一條邊對應到矩陣的兩個1
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? 請列舉出來。
4.4 The Incidence Matrix of a Graph e1 e2 e3 e4 e5 e6 u1 u2 u3 u4 u5 紀錄「點」與「邊」的關係
4.7 Minimum Cost Spanning Trees Definition 4.36
Definition 4.37
Example 每一步挑選weight最小且加入後不形成cycle的邊 T1= T3 T2 y x w u v 2 5 4 3 1 6 G
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
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
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
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