4.3 - Spanning Tree

1. Spanning Tree

$G=(V, E)$ 是一個Connected的Undirected Graph，令 $S=(V, T)$是G的一個Spanning Tree:

1. $E=T+B \Rightarrow T=E-B$

   T: Tree edge；B: Back edge

2. 自B中挑選一個邊加入S中，必在S中形成一個cycle。

3. 在S中的任何頂點對之間，存在一條唯一的Simple Path。

e.g.

DFS Spanning Tree BFS Spanning Tree

1. 任何Connected Undirected Graph至少有一棵Spanning Tree

2. 若Connected Undirected Graph有v個頂點，則Spanning Tree的邊數必為v-1條邊

3. 若將Binary Tree視為無向圖，則它的Spanning Tree只有一棵

4. 若為unconnected graph，則必無Spanning Tree

2. Min Spanning Tree(最小成本展開樹)

Connected Undirected Graph $G=(V, E)$ 的每個邊上cost值，則在Ｇ的所有spanning trees中具有邊成本總和最小者。

1. min spanning tree ≥ 1

2. 若G中每個邊的成本皆不同，則最小成本展開數樹只有一棵

求法:

1. Kruskal's algorithm

2. Prim's algorithm

3. Sollin's algorithm