树(离散数学)

1.无向树及其性质

定义7.1.1 无向树及相关概念

设图$G=(V,E)$为无向图：

1. 无向树（树）
   连通且不含回路的无向图
2. 森林
   各连通分支都是树的无向图
3. 平凡树
   仅含单个顶点的平凡图
4. 树叶
   无向树中度为1的悬挂顶点
5. 分支点
   无向树中度数$\geq 2$的顶点

特别说明：

• 定义中的"回路"特指初级回路（简单回路）
• 本章后续讨论默认遵循此回路定义

定理7.1.1 树等价命题

设$G=\langle V,E \rangle$为$n$阶$m$边无向图，下列命题等价：

1. 树定义：$G$是树
2. 唯一路径性：$G$中任意两顶点存在唯一路径
3. 无圈边数条件：$G$无回路且$m = n - 1$
4. 连通边数条件：$G$连通且$m = n - 1$
5. 全桥连通性：$G$连通且所有边均为桥
6. 加边成圈性：
   • $G$不含回路
   • 任意两不同顶点间添加新边后，存在唯一含新边的圈

定理7.1.2 树叶存在定理

对任意$n$阶非平凡无向树$T$（$n \geq 2$），必满足：

等价关系可视化

2.生成树

7.2.1 核心定义

1. 生成树（定义7.2.1）
   • 设无向图 $G$ 的生成子图 $T$ 是树，则称 $T$ 为 $G$ 的生成树。
   • 树枝：$G$ 中属于 $T$ 的边。
   • 弦：$G$ 中不属于 $T$ 的边。
   • 余树：由所有弦构成的导出子图，记作 $\overline{T}$。

7.2.2 生成树的存在性与性质

1. 定理7.2.1
   • 无向图 $G$ 存在生成树的充要条件是 $G$ 为连通图。

2. 推论7.2.1
   • 设 $G$ 为 $n$ 阶 $m$ 条边的无向连通图，则 $m \geq n-1$。

7.2.3 基本回路系统

1. 定义7.2.2
   • 设 $T$ 是 $n$ 阶 $m$ 边连通图 $G$ 的生成树，其弦数为 $m-n+1$。
   • 对每条弦 $e_r$，由 $T$ 添加 $e_r$ 形成的唯一圈 $C_r$ 称为 基本回路。
   • 所有基本回路组成的集合 $\{ C_1, C_2, \dots, C_{m-n+1} \}$ 称为 $G$ 的 基本回路系统。
   • 圈秩：$\xi(G) = m - n + 1$，表示图的回路复杂度。

2. 广义回路空间
   • 广义回路：圈或边不重的圈的并（包括空集）。
   • 全体广义回路 $C^*$ 在环和运算与数乘 $(0 \cdot C = \varnothing, 1 \cdot C = C)$ 下构成 $F_2$ 上的 $\xi(G)$ 维线性空间。
   • 基：任一基本回路系统均为其基。

7.2.4 基本割集系统

1. 定理7.2.3
   • 设 $T$ 是连通图 $G$ 的生成树，$e$ 为树枝，则存在仅含 $e$ 和若干弦的 唯一割集。

2. 定义7.2.3
   • 设 $T$ 是 $n$ 阶连通图 $G$ 的生成树，树枝为 $e_1, e_2, \dots, e_{n-1}$。
   • 每个树枝 $e_i$ 与弦构成的割集 $S_i$ 称为 基本割集。
   • 所有基本割集组成的集合 $\{ S_1, S_2, \dots, S_{n-1} \}$ 称为 基本割集系统。
   • 割集秩：$\eta(G) = n-1$，表示图的割集复杂度。

3. 广义割集空间
   • 广义割集：非空顶点子集补集间的边集（包括空集）。
   • 全体广义割集 $S^*$ 在对称差运算与数乘 $(0 \cdot S = \varnothing, 1 \cdot S = S)$ 下构成 $F_2$ 上的 $\eta(G)$ 维线性空间。
   • 基：任一基本割集系统均为其基。

7.2.5 最小生成树与算法

1. 定义7.2.4
   • 设无向连通带权图 $G = (V, E, W)$，生成树 $T$ 的权为各边权之和 $W(T)$。
   • 最小生成树：权最小的生成树。

2. Kruskal算法（避圈法）
   • 输入：$n$ 阶无环连通带权图 $G$，边集 $E = \{ e_1, e_2, \dots, e_m \}$（按权升序排列）。
   • 步骤：

   1. 初始化 $T = \varnothing$。
   2. 依次检查每条边 $e_j$：
      ▪ 若 $e_j$ 加入 $T$ 后不形成回路，则加入 $T$。
      ▪ 否则舍弃 $e_j$。
   3. 当 $T$ 含 $n-1$ 条边时停止，输出最小生成树 $T$。

关键总结

1. 生成树与连通性：生成树存在等价于图连通，且边数下限为 $n-1$。
2. 对偶结构：
   • 回路系统（圈秩 $\xi(G) = m - n + 1$）
   • 割集系统（割集秩 $\eta(G) = n - 1$）
3. 线性空间：
   • 广义回路空间（维数 $\xi(G)$）
   • 广义割集空间（维数 $\eta(G)$）
4. 最小生成树算法：Kruskal算法通过贪心选择避免回路，逐步构造最优解。

3 根树及其应用

7.3.1 根树基本定义

定义7.3.1
设图$G$为有向图：

• 有向树：基图为无向树的有向图
• 根树：存在唯一入度为0的顶点（树根），其余顶点入度均为1的有向树
• 顶点分类：
  • 树根：入度为0的顶点
  • 树叶：入度为1且出度为0的顶点
  • 内点：入度为1且出度不为0的顶点
  • 分支点：树根与内点的统称
• 层数与树高：
  • $v$的层数：树根到$v$的路径边数
  • 树高：所有顶点的最大层数

7.3.2 根树关系与分类

定义7.3.2
设$T$为根树：

• 亲属关系：
  • 祖先/后代：顶点间存在可达路径的纵向关系
  • 父/子：直接邻接的顶点间关系
  • 兄弟：同一父节点的子节点
• 有序树：对同层顶点指定顺序的根树
• 分类体系

定义7.3.3

• 根子树：以任意顶点$v$及其后代构成的子树
• 二叉正则有序树：
  • 左子树：分支点第一个儿子导出的子树
  • 右子树：分支点第二个儿子导出的子树

7.3.3 最优二叉树

定义7.3.4
设二叉树$T$有$t$片树叶$v_1,\dots,v_t$，权值为$w_1,\dots,w_t$：

• 权计算公式： $$W(T) = \sum_{i=1}^t w_i \cdot l(v_i)$$ 其中$l(v_i)$为$v_i$的层数
• 最优二叉树：在相同权值集合中，权值$W(T)$最小的二叉树

7.3.4 霍夫曼算法

算法步骤：

1. 初始化：创建$t$片树叶，权值为$w_1,\dots,w_t$
2. 迭代合并：
   • 选择权最小的两个入度为0顶点
   • 创建新分支点，权为子节点权之和
3. 终止条件：只剩1个入度为0顶点（树根）
4. 权值特性：$W(T)$等于所有分支点权之和

7.3.5 前缀码

定义7.3.5

• 前缀：符号串$\alpha_1\alpha_2\cdots\alpha_n$的子串$\alpha_1,\ \alpha_1\alpha_2,\ \dots,\ \alpha_1\cdots\alpha_{n-1}$
• 前缀码：符号串集合$A$中任意两元素互不为前缀
• 二元前缀码：由0/1符号串构成的前缀码

7.3.6 二叉正则树应用示例

算式表示：
表达式$(a*(b+c)+d*e*f)\div(g+(h-i)*j)$的二叉树表示：

         ÷
       /   \
      ◦     +
     / \   / \
    ◦   * g   *
   / \  |    / \
  a  +  d   -   j
    / \     / \
   b c     h i

行遍法结果：

符号说明：

• $\star$表示乘法运算
• 括号标记运算优先级
• 遍历结果需配合运算符优先级规则解析