# 树

设 G=(V,E) 是无向图，若 G 是连通的并且无圈，则称 G 为自由树，树中的边称为树枝，若 deg (v)=1，称 v 为叶子，否则称为分枝点或树杈。

# 定理 1

设 G=(V,E) 是 (n,m) 无向图，下面六种说法是等价的：

1. G 是一棵树；
2. G 的每一对结点间有且只有一条路；
3. G 是连通的并且 m=n-1；
4. G 是无圈的并且 m=n-1；
5. G 是无圈的但若在 G 的任一对结点间加一条边，则 G 中有一个圈；
6. G 是连通的但若在 G 中任意删除一条边，则 G 有两个连通支。

# 森林

设 G=(V,E) 是无向图，若 G 是无圈，则称 G 为一个森林。

# 生成树或支撑树 (shanning tree)。

设 G=(V,E) 是无向图，G̃=(V,Ẽ) 是 G 的生成子图，若 G̃是一棵树，则称 G̃ 是 G 的一棵生成树或支撑树 (shanning tree)。

# 定理 2

设 G=(V,E) 是无向图。则 G 有生成树$\iff$G 是连通图。

# “管氏破圈” 算法：

1. 若 G 中无圈，exit 。G 即为生成树；
2. G 中有圈 C，在圈 C 上任意删去一边 e；令 G:=G {e}，goto No1 。

# “Kruskal 避圈” 算法：

设$G=( V, E ) ，E={e_1, e_2,...,e_m}$。

1. T:={e1}，i:=1，k:=1 ；
2. i:=i+1，若$T\cup \{e_i\}$ 无圈，则令$T:=T\cup \{e_i\}$， k:=k+1 ；
3. 若 k=n-1 或 i=m，exit ；否则，goto No2 。

# 生成树

设 G=(V, E, w) 是连通的无向带权图，设 T={e1,e2,…,en-1} 是 G 的一棵生成树 ， T 的总权和为：

$$w(T)=\sum^{n-1}_{i=1}w(e_i)$$

若有 G 的一棵生成树 T0，使其总权和 w (T0) 在诸生成树中达到最小，即 w (T0)=min {w (T) | T 是 G 的生成树}，则称 T 是 G 的最小生成树或最优树 。