CHT 10-Tree Graphs

[! 定义]
树：连通无回路的图

树叶：树中度为1的点

分枝点或内点：度大于1的点

森林：每个连通分支均为树的图

[! 定理1 ]
设图T是有n个顶点、$\varepsilon$条边的非平凡图，则下列各条等价。

(1) T是树。

(2) T中无回路，且$\varepsilon = n - 1$。

(3) T连通，且$\varepsilon = n - 1$。

(4) T中无回路，且在T的任意两个不相邻点之间添加一边恰得一条回路。

(5) T连通，删去任一边则不连通。

(6) T的任意两个不同顶点之间恰有一条路。

验证
(5)(6) 容易得
不难，其中(2)或(3)可用数学归纳法

例题若干

[! 定义]
若图G的生成子图T是树，则称T为G的生成树 Spanning Tree 。

生成树的概念是相当有用的，特别是最小生成树。因为这代表了保持连通性的最小子图。
最小生成树唯一？未必吧，存在权重相同的边时。

关于最小生成树，常见的有两种求取算法：

• 权图$G$中带权最小的生成树称为最小生成树 Minimal Spanning Tree
• 克鲁斯克尔（Kruskal）算法，它是一种避圈法，其基本思想是：选择图中权最小的一条边，相继添加不与已经选择的边形成圈的权最小的边，挑选$n-1$条边为止（其中$n$为结点的个数）。
• 普里姆（Prim），它是一种“逐步短接”的思想，其基本思想是：选择图中与$V(T)$邻接且权最小的一条边，将该边加入到$T$中且不形成回路，相继选择$n-1$条边为止（其中$n$为结点的个数）。