本章记录无向树、生成树、根树和相关证明。很多结论和算法竞赛里的树很接近，但离散数学会更重视定义与等价条件。

无向树及其性质

连通无回路的无向图称为无向树，简称为树。每个连通分支都是树的无向图称为森林。平凡图称作平凡树。悬挂顶点称作树叶，度数大于等于2的顶点称作分支点。

设 $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$ 中没有回路，但在任意两个顶点之间加一条新边后所得的图中有唯一的一个含新边的圈。

它们的证明很有意思，采用了本书中曾见过的循环证明。

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

画非同构的无向树时，通常先枚举叶子数量与度数列。 只有一个分支点，且分支点的度数为 $n-1$ 的 $n$ 阶无向树为星形图，称其唯一的分支点为星心。

生成树

如果无向图 $G$ 的生成子图是树，那么称 $T$ 是 $G$ 的生成树。设 $T$ 是 $G$ 的生成树， $G$ 中且在 $T$ 中的边称作 $T$ 的树枝，不在 $T$ 中的边称作 $T$ 的弦。称 $T$ 的所有弦的导出子图为 $T$ 的余树，记作 $\overline{T}$。

定理：无向图 $G$ 有生成树 $\Leftrightarrow$ $G$ 为连通图。

推论：设 $G$ 为 $n$ 阶 $m$ 条，则 $m \ge n-1$。

定理：设 $T$ 为无向图 $G$ 中的一棵生成树， $e$ 为 $T$ 的任意一条弦，则 $T \cup e$ 中存在 $G$ 中只含一条弦 $e$ 、其余边均为树枝的圈，并且不同的弦对应的圈也不同。

导出以下定义：

设 $T$ 是 $n$ 阶 $m$ 条边的无向连通图 $G$ 的一棵生成树，设 $e_1’,e_2’,\ldots,e_{m-n+1}’$ 为 $T$ 的弦， $C_r,r=1,2,\ldots,m-n+1$ 为 $T$ 添加弦 $e_r’$ 产生的 $G$ 中由弦 $e_r’$ 和树枝构成的圈，称其为 $G$ 的对应弦 $e_r’$ 的基本回路或基本圈。称 $\lbrace{}C_1,C_2,\ldots,C_{m-n+1}\rbrace$ 为 $G$ 对应 $T$ 的基本回路系统，称 $m-n+1$ 为 $G$ 的圈秩，记作 $\xi(G)$。

无向连通图 $G$ 的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。 可以证明：任意简单回路都可以表示成基本回路的环和。 我们称无向图中的圈或若干个边不重的圈的并，称作广义回路。规定 $\emptyset$ 为广义回路，圈和简单回路都是广义回路。记无向图 $G$ 的广义回路的全体为 $C^$。 两个广义回路的环和仍是广义回路。定义数乘运算为 $0 \cdot C = \emptyset,1 \cdot C = C$。 则 $C^$ 构成数域 $F$ 上的 $m-n+1$ 线性空间，称作广义回路空间。任意基本回路系统均是它的一个基。 设计电网络不需要考虑电网络中的所有圈，而只需要考虑任一生成树的基本回路。 定理：设 $T$ 是连通图 $G$ 的一棵生成树， $e$ 为 $T$ 的树枝，则 $G$ 中存在只含树枝 $e$ ，其他边都是弦的割集。 构造性证明，构造的这个可以记一下。 于是我们可以导出以下定义： 设 $T$ 是 $n$ 阶 $m$ 条边的无向连通图 $G$ 的一棵生成树，设 $e_1,e_2,\ldots,e_{m-n+1}$。 为 $T$ 的树枝， $S_i,i=1,2,\ldots,{n-1}$ 是由树枝 $e_i$ 和弦构成的割集，则称 $S_i$ 为 $G$ 的对应树枝 $e_i$ 的基本割集。称 $\lbrace{}S_1,S_2,S_{n-1}\rbrace$ 为 $G$ 对应 $T$ 的基本割集系统，称 $n-1$ 为 $G$ 的割集秩，记作 $\eta(G)$。 连通图 $G$ 的 $\eta(G)$ 不因生成树的不同而改变，但不同生成树对应的基本割集系统可能改变。 设无向图 $G=\langle V,E \rangle,\emptyset \not = V_1 \subset V,$ 记 $V_1$ 关于 $V$ 的补集为 $\overline{V_1},$ 称 $(V_1,\overline{V_1})=\lbrace(u,v) | u \in V_1,v \in \overline{V_1}\rbrace$ 为广义割集。规定 $\emptyset$ 为广义割集。显然，割集一定是广义割集，但是广义割集不一定是割集。任意广义割集都可以表示成基本割集的对称差。记无向图 $G$ 的广义割集的全体为 $S*,$ 它关于对称差运算和数乘运算构成数域 $F$ 上的 $n-1$ 维线性空间，称作广义割集空间。任意基本割集系统均是它的一个基。

对于无向连通带权图 $G=\langle V,E,W \rangle,T$ 是 $G$ 的一棵生成树，其各边权之和称为 $T$ 的权，记作 $W(T)$。 它的所有生成树中权最小的生成树称为 $G$ 的最小生成树。 求最小生成树：$\mathrm{Kruscal}$ 算法，又称作避圈法。 一个最小生成树的应用：数据分析中的单链聚类。 给定一组离散数据 $D=\lbrace{}d_1,d_2,\ldots,d_n\rbrace$ 和一个相似度函数 $d(i,j)$。给定正整数 $k$ ，求它的一个k聚类，即一个 $k$ 划分

$$ \pi=\lbrace{}C_1,C_2,\ldots,C_k\rbrace $$

规定

$$ D(C_s,C_t)=\mathrm{min}\lbrace{}d(i,j) | a_i \in C_s,a_j \in C_t\rbrace $$

以及

$$ D(\pi)=\mathrm{min}\lbrace{}D(C_s,C_t) | C_s,C_t \in pi,1 \le s < t \le k\rbrace $$

求使 $D(\pi)$ 达到最大值的 $\pi$ ？ 我们采用 $\mathrm{Kruscal}$ 算法处理这个问题。把边按照权进行排序，逐渐加到原来的连通分支中，当 $k$ 个连通分支时停止，此时最小间隔达到最大。

根树及其应用

若有向图的基图为无向树，则称这个有向图为有向树。一个顶点的入度为0，其余顶点的入度为1的有向树称为根树。入度为0的顶点称为树根。入度为1、出度为0的顶点称作树叶，入度为1、出度不为0的顶点称为内点，根点和内点统称为分支点。从树根到任意顶点 $v$ 的路径的长度称作 $v$ 的层数，所有顶点的最大层数称为树高。

常将根树看做家族树。 定义：设 $T$ 为一棵非平凡的根树， $\forall v_i,v_j \in V(T),$ 若 $v_i \rightarrow v_j,$ 称 $v_i$ 为 $v_j$ 的祖先， $v_j$ 为 $v_i$ 的后代。若它们邻接，则称为父亲/儿子，若 $v_j,v_k$ 的父亲相同，称它们为兄弟。 定义：若 $T$ 为根树，且 $T$ 中层数相同的顶点都标定次序，称其为有序树。 若 $T$ 的每个分支点至多有 $r$ 个儿子，称其为 $r$ 叉树；若是有序树，称其为 $r$ 叉有序树。 若 $T$ 的每个分支点都恰好有 $r$ 个儿子，称其为 $r$ 叉正则树；若是有序树，称其为 $r$ 叉正则有序树。 若 $T$ 是 $r$ 叉正则树，且每个树叶的层数都为树高，称其为 $r$ 叉完全正则树；若是有序树，称其为 $r$ 叉完全正则有序树。

根子树、左子树、右子树的概念

定义：设 $T$ 有 $t$ 片树叶 $v_1,v_2,\ldots,v_t,$ 它们的点权为别为 $w_1,w_2,\ldots,w_t,$ 令 $W(T)=\sum\limits_{i=1}^{t}w_il(v_i),l(v_i)$ 为 $v_i$ 的层数，给定 $t$ 和 $w_1,w_2,\ldots,w_t,$ 的二叉树中，权最小的二叉树称为最优二叉树。 求最优二叉树：霍夫曼($\mathrm{Huffman}$ )算法。 把全部的叶子写在一起，取其中权值最小的两个，连起来，它们的父亲的权值是它们权值之和，如此往复。

在通信中，常用二进制编码表示符号，有等长码表示法。当符号的频率相差悬殊时，为了节省二进制数位，提高效率，采用非等长的编码。 设 $\alpha_1\alpha_2\ldots \alpha_n$ 是长为 $n$ 的符号串，称其子串 $\alpha_1,\alpha_1\alpha_2,\ldots,\alpha_1\alpha_2\ldots \alpha_n$ 为该符号串的前缀。设 $A=\lbrace\beta_1,\beta_2,\ldots,\beta_m\rbrace$ 是一个符号串集合，若 $A$ 的任意两个符号串都互不为前缀，称 $A$ 为前缀码，由 $0,1$ 符号串组成的前缀码为二元前缀码。 可以用二叉树产生二元前缀码。设 $T$ 是具有 $n$ 片树叶的二叉树，则 $T$ 的每个分支点有 $1$ 或 $2$ 个儿子．设 $v$ 为 $T$ 的分支点，若 $v$ 有两个儿子，在由 $v$ 引出的两条边上，左边的标 $0$ ，右边的标 $1$。若 $v$ 只有一个儿子，由它引出的边可以标 $0$ ，也可以标 $1$ ．设 $v_i$ 是 $T$ 的任意一片树叶，从树根到 $v_i$ 的通路上各边的标号（ $0$ 或 $1$ ）按照通路上边的顺序组成的符号串放在 $v_i$ 处， $t$ 片树叶的 $t$ 个符号串组成一个二元码．由此方法可知，树叶 $v_i$ 处的符号串的前缀均在从树根到 $v_i$ 的通路上的顶点（不含 $v_i$ ）处达到，因而所得符号串集合必为前缀码．若 $T$ 是二叉正则树，则由 $T$ 产生的前缀码是唯一的．或者说，由一棵二叉正则树可以产生唯一的一个二元前缀码。

给定每个 $v_i$ 出现的频率 $c_i$ ，要求 $m$ 个符号使用的二进制位数 $m\sum\limits_{i=1}^{t}c_il(v_i)$。 我们可以用最优二叉树来产生它的前缀码，如此产生的前缀码称为最优前缀码，最优前缀码传输的二进制位数最少。 例题可以看书，比如给定百分比频率就假设 $100$ 个符号，最后再按比例来。

最佳前缀码并不唯一，因为每一步选择两个最小权的选法可能不唯一，同时两个权对应顶点的左右位置也可以不同。

周游/行遍/遍历都是一个意思。 前序：根左右。 中序：左根右。 后序：左右根。

利用二叉正则有序树表示四则运算算式：运算的树放在树叶，运算符放在分支点，被除数和被减数放在左边。 前缀符号法/前序遍历/波兰符号法：从右到左每个运算符对它后面紧邻的两个数进行运算。 后缀符号法/后序遍历/逆波兰符号法：从左到右每个运算符对它前面紧邻的两个数进行运算。

下面整理一些容易漏条件的题目。

1. 给定一个无向图，请求出其所有非同构的生成树。

一般做法：先不管原图，按照顶点数写出所有可能的度数列和非同构树，然后再按照最大度数等对写出来的进行删减，最后去原图中找。

2. 画出给定无向树中派生的所有非同构根树。

对称的顶点作为树根时是同构的。

3. 设 $T$ 是 $6$ 阶无向简单图 $G$ 的一棵生成树，讨论以下问题。 (1)当 $G$ 的边数 $m$ 为 $9$ 时， $T$ 的余树 $\overline{T}$ 还有可能是 $G$ 的生成树吗？ (2)当 $G$ 的边数 $m$ 为 $12$ 时， $T$ 的余树 $\overline{T}$ 还有可能是 $G$ 的生成树吗？ (3)当 $G$ 的边数 $m$ 为 $12$ 时， $T$ 的余树 $\overline{T}$ 有哪几种情况？

$6$ 阶生成树一定有 $5$ 条边。(1)(2) 都可以先从边数入手排除。至于 (3)，$\overline T$ 可能仍是原图的一棵生成树，也可能形成圈，也可能不连通。

4. 高为 $h$ 的 $r$ 叉正则树至多有 $r^h$ 片树叶，至少有 $(r-1)(h-1)$ 片树叶。

5. $G$ 为 $n$ 阶 $m$ 条边的无向简单连通图，若 $m \ge n,$ 则 $G$ 中必含圈。

6. 设 $d_1,d_2,\ldots,d_n$ 是 $n$ 个正整数，$\sum\limits_{i=1}^{n}d_i=2n-2,n \ge 2$。证明：存在无向树 $T$ 以 $(d_1,d_2,\ldots,d_n)$ 为度数列。

用构造性归纳法。先注意到，当 $n\geq 3$ 时，度数列中至少有一个 $1$，也至少有一个大于等于 $2$ 的数。

$n=2$ 时结论显然成立。假设 $n=k$ 时命题成立。考虑 $n=k+1$ 的情形，不妨设 $d_k\geq 2,d_{k+1}=1$。由归纳假设，度数列

$$ (d_1,d_2,\ldots,d_k-1) $$

可以构成一棵无向树。现在增加一个新顶点，并把它连接到原来度数为 $d_k-1$ 的顶点上，得到的新图仍连通且无回路，因此是一棵树，且度数列正好为原来的 $(d_1,d_2,\ldots,d_k,d_{k+1})$。

7. 画出所有 $7$ 阶非同构的无向树。

一般步骤是：先由边数确定总度数，再列出可能的度数列，最后按度数列画图并排除同构。画图时，度数为 $2$ 的顶点常常起到“连接口”的作用：它既可能连接两个较大的分支，也可能连接分支点和树叶。另一个容易漏掉的情况是，一个高分支度顶点也可能接在另一个高分支度顶点下面。

8. $n$ 阶无向树 $T$ 的 $\Delta(T)$ 至少为 $2$ ，至多为 $n-1$。若 $\Delta(T)=2,$ 则最长的路径长为 $n-1$。 $n$ 阶无向树不是欧拉图，也不是哈密顿图。

平凡图是树，也是欧拉图，也是哈密顿图。当 $\Delta(T)=2$ 时，无向树为半欧拉图和半哈密顿图。

9. 证明：任何无向树都是二部图。

无向树不含任何圈，自然也不含奇圈。由二部图判定定理，无奇圈的无向图是二部图，因此任何无向树都是二部图。

10. 设 $e$ 为无向连通图 $G$ 中的一条边，若 $e$ 在 $G$ 的任何生成树中，则 $e$ 应该有什么性质？

证明：$e$ 应为 $G$ 的桥。若 $e$ 是 $G$ 的桥，若存在生成树 $T$ 不包含 $e$ ，则 $T$ 不连通，与树的连通性矛盾。若 $e$ 不是 $G$ 的桥，则 $G-e$ 包含了 $G$ 的全部顶点且连通，因此 $G-e$ 中存在生成树。综上， $e$ 是 $G$ 的桥。

11. 设 $e$ 为无向连通图 $G$ 的一条边。若 $e$ 不在 $G$ 的任何生成树中，则 $e$ 应该有什么性质？

证明：$e$ 应为 $G$ 的环。若 $e$ 是 $G$ 的环，若存在生成树 $T$ 包含 $e$ ，则 $T$ 存在回路，与其无回路的性质矛盾。若 $e$ 不是 $G$ 的环，则必然存在某棵生成树包含 $T$。综上， $e$ 是 $G$ 中的环。

12. 设 $e$ 为无向连通图 $G$ 中的一条边， $e$ 既不是环，也不是桥。证明：存在含 $e$ 为树枝的 $G$ 的生成树，又存在以 $e$ 为弦的 $G$ 的生成树。

下面我们介绍一种求生成树的方法：破圈法，即有圈就在圈中删掉一条边的方法。它无法用来求最小生成树。

我们的证明与它有关。

证明：由于 $e$ 不是桥，因此 $e$ 在某个圈中，又由于 $e$ 不是环，因此这个圈的长度大于等于2。

在用破圈法生成生成树时，无论 $e$ 在哪个圈中出现，删除一条边时都不删掉 $e,$ 这样得到的生成树含 $e$ 作为树枝。

在用破圈法生成生成树时，找到一个含 $e$ 的圈，将 $e$ 从其中删除，于是得到了一个 $e$ 为弦的生成树。

13. 设 $T$ 为无向图 $G$ 的生成树， $\overline{T}$ 为 $T$ 的余树，则 $\overline{T}$ 中不含 $G$ 的边割集。

设 $S$ 为无向连通图 $G$ 的一个边割集，则 $G-S$ 中不含 $G$ 的生成树。

14. 求 $K_n$ 的非同构生成树数量的步骤与求 $n$ 阶非同构生成树数量相同。

15. 设 $T$ 为 $k+1$ 阶无向树，$k \ge 1$。$G$ 是无向简单图，已知 $\delta(G) \ge k$，证明：$G$ 中存在与 $T$ 同构的子树。

用归纳法，并结合树叶的构造。不妨在 $G$ 的某个连通分支中讨论。

$k=1$ 时结论显然成立。设 $k=r$ 时命题成立，下面证明 $k=r+1$。树 $T$ 至少有两片树叶，取其中一片为 $v_0$，设它唯一相邻的顶点为 $v_1$。由归纳假设，$T-v_0$ 可以嵌入到 $G$ 的某个子图 $G’$ 中。设 $v_1$ 在 $G’$ 中对应的顶点为 $u_1$。

由于 $d_G(u_1)\geq r+1$，而 $G’$ 中至多已经使用了 $r$ 个与 $u_1$ 有关的顶点，因此可以在 $G$ 中找到一个尚未使用的顶点 $u_0$ 与 $u_1$ 相邻。把 $u_0$ 接到 $u_1$ 上，就得到一个与 $T$ 同构的子树。

16. 已知 $n$ 阶 $m$ 条树是 $k$ 棵树组成的森林，则 $m=n-k$。

17. 设 $T$ 为非平凡的无向树，$\Delta(T) \ge k$，证明：$T$ 至少有 $k$ 片树叶。

设 $T$ 有 $s$ 片树叶，取一个度数至少为 $k$ 的顶点。其余非叶顶点的度数至少为 $2$，于是度数和满足

$$ 2(n-s-1)+k+s \leq 2(n-1) $$

化简得到 $s\geq k$。

18. 设 $G$ 为 $n(n \ge 5)$ 阶简单图，证明：$G$ 或 $\overline{G}$ 中必含圈。

若 $G$ 与 $\overline G$ 都无圈，则它们都是森林，边数都不超过 $n-1$。但 $G$ 与 $\overline G$ 的边数之和为完全图 $K_n$ 的边数，即

$$ |E(G)|+|E(\overline G)|=\frac{n(n-1)}{2} $$

当 $n\geq 5$ 时

$$ 2(n-1)<\frac{n(n-1)}{2} $$

矛盾。因此 $G$ 或 $\overline G$ 中必含圈。

19. 设 $C$ 为无向图 $G$ 中的一个圈， $e_1,e_2, \in E(C),$ 证明：$G$ 中存在含边 $e_1,e_2$ 的割集。

思路：这种题一般是考虑生成树。

证明：不妨设 $G$ 为连通图，否则可以对某个连通分支进行讨论。

对于 $G-e_1,$ 考虑使用破圈法时，总不删除 $e_2$ ，则最后得到一棵只含 $e_2$ 不含 $e_1$ 的生成树，此时 $e_1,e_2$ 都属于 $e_2$ 对应的基本割集。

20. 设 $T_1,T_2$ 是无向图 $T$ 的子图，并且都是树，又已知 $E(T_1) \cap E(T_2) \neq \emptyset$，证明：导出子图 $G[E(T_1) \cap E(T_2)]$ 也是树。

记这个导出子图为 $T_3$。由于 $T_1,T_2$ 都无回路，$T_3$ 也无回路。下面证明它连通。任取 $T_3$ 中两个顶点 $u,v$，它们在 $T_1$ 中有唯一通路，在 $T_2$ 中也有唯一通路。由于这两条通路都位于原树 $T$ 中，而树中两点之间的通路唯一，因此二者相同，并且这条通路的每条边都属于 $E(T_1)\cap E(T_2)$。所以 $T_3$ 连通，从而是树。

21. 设 $T_1,T_2$ 是无向连通图 $G$ 的两棵生成树，已知 $e_1$ 是 $T_1$ 的树枝又是 $T_2$ 的弦，证明：存在边 $e_2$ 既是 $T_1$ 的弦又是 $T_2$ 的树枝，使得 $(T_1-e_1) \cup \lbrace{}e_2\rbrace$ 和 $(T_2 - e_2) \cup \lbrace{}e_1\rbrace$ 都是 $G$ 的生成树。

思路：这个题目我看了有点久，它利用了很多上面我们讲到的性质。

证明：由于 $e_1$ 是 $T_1$ 的树枝，因此 $e_1$ 不是环(因为环不存在于任何生成树中)，同时设 $e_1$ 对应的 $T_2$ 的基本回路为 $C_1$ ，有 $|C_1| \ge 2$。 由于 $e_1$ 是 $T_2$ 的弦，因此 $e_1$ 不是桥(因为桥包含于任何生成树中)。同时设 $e_1$ 对应的基本割集为 $S_1,$ 有 $|S_1| \ge 2$。 考虑 $C_1$ 中 $T_2$ 的树枝，若它们都不在 $S_1$ 中，则 $G-S_1$ 中 $e_1$ 的两个顶点之间有通路，因此与割集矛盾。于是，存在 $e_2$ 既是 $T_1$ 的弦又是 $T_2$ 的树枝。

综上所述，由于 $e_2 \in S_1$，由割集的定义，$(T_1-e_1) \cup \lbrace{}e_2\rbrace$ 连通且无回路，为生成树；又由于 $e_2 \in C_1$，$(T_2 - e_2) \cup \lbrace{}e_1\rbrace$ 连通且无回路，也为生成树。最后这一段不太好理解。

22. 设 $T$ 是有 $t$ 片树叶的二叉正则树，证明：$T$ 有 $2t-1$ 个顶点。

设 $T$ 一共有 $n$ 个顶点，则非叶顶点有 $n-t$ 个。二叉正则树中每个非叶顶点都有两个儿子，因此边数为 $2(n-t)$。另一方面，树的边数为 $n-1$，所以有

$$ 2(n-t)=n-1 $$

化简得 $n=2t-1$。