树

无向树

定义

无向树：连通无回路的无向图，记作 T。平凡树是平凡图。森林是至少由两个连通分支（每个都是树）组成的图。树叶是度数为 1的顶点，分支点是度数 $\geq 2$ 的顶点。

等价定义与性质

定理：设 $G = ⟨ V, E ⟩$ 是 n 阶 m 条边的无向图，以下命题等价：

G 是树。
G 中任意两个顶点之间存在唯一的路径。
G 中无回路且 $m = n - 1$ 。
G 是连通的且 $m = n - 1$ 。
G 是连通的且 G 中任何边均为桥。
G 中没有回路，但在任何两个不同的顶点之间加一条新边，所得图中得到唯一的一个含新边的圈。

定理：T 是 n 阶非平凡的无向树，则 T 中至少有两片树叶。

推论：具有 k 个分支的森林有 n-k 条边。

定理：设正整数序列 $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ ， $\sum d_{i} = 2 (n - 1)$ ，则存在一棵树 T其度序列为该序列。

中心与形心

中心：

离心率：一个顶点到其他顶点距离的最大值。
半径：最小离心率。
直径：最大离心率。
中心点：离心率等于半径的点。
中心：中心点的集合。

定理：每棵树的中心由一个点或两个相邻点组成。

形心：

权：一个顶点的分支中边的最大数目。
形心点：权最小的点。
形心：全体形心点的集合。

定理：每一棵树有一个由一个点或两个邻接的点组成的形心。

生成树

定义

设 G 为无向图：

G 的树：T 是 G 的子图且是树。
G 的生成树：T 是 G 的生成子图且是树。
树枝：生成树 T 中的边。
弦：不在生成树 T 中的边。
余树：全体弦组成的集合的导出子图（不一定连通，也不一定不含回路）。

定理：无向图 G 具有生成树当且仅当 G 连通。

推论：G为 n阶 m条边的无向连通图，则 $m \geq n - 1$ 。余树的边数为 $m - n + 1$ 。

生成树的计数

Cayley 定理：设 e 是 G 的一条边，G 的生成树中包含边 e 的棵数为 $G ∖ e$ ，不包含 e 的棵数为 $G - e$ 。

矩阵树定理：设 G 的顶点集为 ${v_{1}, v_{2}, \dots, v_{n}}$ ， $A = (a_{ij})$ 为邻接矩阵， $C = (c_{ij})$ 为 n 阶方阵，则 G 的生成树棵数为 C 的任意一个余子式的值。

基本回路与基本割集

基本回路

设 T是连通图 G的一棵生成树，e为 T的任意一条弦，则 $T \cup e$ 中含一个具有一条弦其余边均为 T的树枝的圈。不同的弦对应的圈不同。

基本回路：由生成树 T 添加弦 $e_{i}$ 产生的只含弦 $e_{i}$ 、其余边均为树枝的圈，记作 $C_{i}$ 。

基本回路系统： ${C_{1}, C_{2}, \dots, C_{m - n + 1}}$ 。

圈秩： $ξ (G) = m - n + 1$ 。

注意：基本回路是回路，即路径的表示。

基本割集

设 T 是连通图 G 的一棵生成树，e 为 T 的树枝，则 G 中存在只含树枝 e、其余边都是弦的割集。

基本割集：由生成树 T 的树枝 $e_{i}$ 生成的只含树枝 $e_{i}$ 的割集，记作 $S_{i}$ 。

基本割集系统： ${S_{1}, S_{2}, \dots, S_{n - 1}}$ 。

割集秩： $η (G) = n - 1$ 。

算法：设 e为生成树 T的树枝， $T - e$ 为两棵小树 $T_{1}$ 与 $T_{2}$ ，令 $S_{e} = {e^{'} \in E (G) ∣ e^{'}$ 的两个端点分别属于 $T_{1}$ 与 $T_{2}}$ ，则 $S_{e}$ 为 e对应的基本割集。

注意：基本割集是割集，即集合的表示。

最小生成树

定义

T 是 $G = ⟨ V, E, w ⟩$ 的生成树，其权 $w (T)$ 为 T 各边权之和。最小生成树是 G 的所有生成树中权最小的。

Kruskal 算法（避圈法）

将 G 中非环边按权从小到大排序： $e_{1}, e_{2}, \dots, e_{m}$ ：

取 e₁ 在 T 中。
检查 $e_{i}$ ，若与 T 中已有边不构成回路则加入，否则弃去。
重复直到得到生成树。

Prim 算法

对于连通赋权图 G 的任意一个顶点 u，选择与 u 关联的权值最小的边作为第一条边 e₁。后续每次在与已选取边只有一个公共端点的所有边中，选取权值最小的边。

破圈法

从赋权图 G 的任意圈开始，去掉该圈中权值最大的一条边，不断破圈，直到 G 中没有圈为止，最后剩下的子图为最小生成树。

根树

定义

T 是有向树（基图为无向树）：

根树：T 中一个顶点入度为 0，其余入度均为 1。
树根：入度为 0 的顶点。
树叶：入度为 1，出度为 0 的顶点。
内点：入度为 1，出度不为 0 的顶点。
分支点：树根与内点的总称。
层数：从树根到该顶点的通路长度。
树高：树中层数最大的顶点的层数。

家族树

在根树中可定义祖先、后代、父亲、儿子、兄弟等关系。顶点 v 及其后代的导出子图称为以 v 为根的根子树。

最优二叉树（哈夫曼树）

定义：设 2叉树 T有 t片树叶，权分别为 $w_{1}, w_{2}, \dots, w_{t}$ ，称 $w (T) = \sum w_{i} l (v_{i})$ 为 T的权（ $l (v_{i})$ 是 $v_{i}$ 的层数）。在所有有 t片树叶、带权 $w_{1}, \dots, w_{t}$ 的 2叉树中，权最小的称为最优 2叉树。