本节对应原书 PDF 第 188–192 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
树是图论中最重要的概念之一. 它在许多领域中，特别是在计算机科学领域中得到了广泛的应用. 本章介绍无向树及有向树的概念、性质及其应用.
在本章开始之前，做一个声明：本章所谈回路均指初级回路或简单回路.
谈到树，自然会想起自然界的树，有树根、树枝、树叶. 在图论中讨论树时，有些术语就来源于自然界的树.
7.1.1 无向树的定义及其性质
定义 7.1 连通不含回路的无向图称为无向树，简称为树. 常用 T 表示一棵树. 每个连通分支都是树的非连通无向图称为森林. 平凡图称为平凡树.
在图 7.1 中，图(a) 为平凡树，图(b) 为 2 棵树组成的森林，图(c) 为 1 棵无向树.
设 T=\langle V,E\rangle 为一棵无向树，v\in V. 若 d(v)=1，则称 v 为 T 的树叶. 图 7.1(c) 中，a,b,c,d 均为树叶. 若 d(v)\geqslant 2，则称 v 为分支点，e,f,g 均为分支点.
图 7.1
下述定理给出树的多条充分必要条件.
定理 7.1 设 G=\langle V,E\rangle，|V|=n，|E|=m. 下面各命题是等价的：
（1）G 连通不含回路（即 G 为树）；
（2）G 的每对顶点之间有唯一的一条路径；
（3）G 是连通的，且 m=n-1；
（4）G 中无回路，且 m=n-1；
（5）G 中无回路，但在 G 的任何两个不相邻的顶点之间增加一条新边，就得到唯一的初级回路；
（6）G 是连通的，但删去任何一条边后，所得图就不连通，即 G 的每条边均为桥.
证明 （1）\Rightarrow（2）. 设 u,v 为 G 中任意两个顶点. 由 G 的连通性，u,v 之间有通路，因而必有路径. 若路径多于一条，必形成回路，这与 G 中无回路矛盾.
（2）\Rightarrow（3）. 由于 G 中任意两个顶点之间均有路径，所以任意两个顶点均是连通的，故 G 是连通的. 下面用第二数学归纳法证明 m=n-1.
当 n=1 时，G 为平凡图，m=0，结论显然成立.
设 n\leqslant k(k\geqslant 1) 时结论成立，证明 n=k+1 时结论也成立. 设 e=(u,v) 为 G 中一条边，由（2）知 u,v 之间除路径 uv 外，无别的通路，因而 G-e 得两个连通分支 G_1 与 G_2. 设它们的顶点数和边数分别为 n_1,n_2 和 m_1,m_2. 易知 n_1\leqslant k 且 n_2\leqslant k. 由归纳假设得 m_1=n_1-1，m_2=n_2-1. 从而 m=m_1+m_2+1=n_1-1+n_2-1+1=n-1.
（3）\Rightarrow（4）. 只要证明 G 中无回路. 若 G 中有回路，从回路中删去任意一条边后，所得图仍然连通，若所得图中再有回路，再从回路中删去一条边，直到所得图中无回路为止. 设共删去 r(r\geqslant 1) 条边所得图为 G'. G' 无回路，但仍是连通的，即 G' 为树. 由（1）\Rightarrow（2）\Rightarrow（3），所以 G' 中 m'=n'-1. 而 n'=n，m'=m-r. 于是得 m-r=n-1，即 m=n-1+r(r\geqslant 1)，这与已知条件矛盾.
（4）\Rightarrow（5）. 由条件（4）易证 G 是连通的. 否则设 G 有 k(k\geqslant 2) 个连通分支 G_1,G_2,\cdots,G_k. 设 G_i 有 n_i 个顶点，m_i 条边，i=1,2,\cdots,k. 由（4）知，每个连通分支都是树，由（1）\Rightarrow（2）\Rightarrow（3），因而 m_i=n_i-1，i=1,2,\cdots,k. 于是 n=n_1+n_2+\cdots+n_k=m_1+1+m_2+1+\cdots+m_k+1=m+k(k\geqslant 2) 这与已知 m=n-1 矛盾. 因而 G 是连通的，又是无回路的，即 G 是树. 由（1）\Rightarrow（2），G 中任意两个不相邻的顶点 u,v 之间存在唯一的路径 P_{uv}，P_{uv} 再加新边 (u,v) 形成唯一的圈.
（5）\Rightarrow（6）. 首先证明 G 是连通的. 否则设 G_1,G_2 是 G 的两个连通分支. v_1 为 G_1 中的一个顶点，v_2 为 G_2 中的一个顶点. 在 G 中加边 (v_1,v_2) 不形成回路，这与已知条件矛盾. 若 G 中存在边 e=(u,v)，G-e 仍连通，说明在 G-e 中存在 u 到 v 的通路. 此通路与 e 构成 G 中回路，这与 G 中无回路矛盾.
（6）\Rightarrow（1）. 只需证 G 中无回路. 若 G 中含回路 C，删除 C 上任何一条边后，所得的图仍连通，与（6）中条件矛盾.
解读：定理 7.1 把「树」的六种说法捆成一件事，好处是做证明时可以挑最顺手的入口：要算边数就用(3)，要证唯一路径就用(2)，要证每条边是桥就用(6)。整条链是循环论证，所以只需按顺序推一圈就完成了全部等价性。
除了由定理 7.1 给出的树的充分必要条件外，树还有下述重要的必要条件.
定理 7.2 设 T=\langle V,E\rangle 是 n 阶非平凡的无向树，则 T 至少有两片树叶.
证明 由树的定义易知，非平凡的树中，任何顶点的度数均大于等于 1. 设 G 中有 k 个 1 度顶点，即 k 片树叶，则其余 n-k 个分支点的度数均大于等于 2. 由握手定理可知
由定理 7.1 知 m=n-1，代入上式，得 k\geqslant 2. 这说明 T 至少有两片树叶.
例 7.1 已知一棵无向树 T 中有 4 度，3 度，2 度的分支点各 1 个，其余的顶点均为树叶，问 T 中有几片树叶？
解 设 T 有 x 片树叶，则 T 的阶数 n=3+x，由定理 7.1 及握手定理得
解出 x=5，即 T 有 5 片树叶.
例 7.2 满足例 7.1 中度数列的无向树在同构的意义下是唯一的吗？
解 在同构意义下不是唯一的. 图 7.2 所示的两棵树的度数列均满足例 7.1，但它们是不同构的.
图 7.2
例 7.3 画出 6 阶所有非同构的无向树.
解 设所求树的顶点数为 n，边数为 m. 由题设已知，n=6.
（1）由无向树的性质可知，m=n-1=5；
（2）由树的定义可知，1\leqslant d(v_i)\leqslant 5，i=1,2,\cdots,5；
（3）由握手定理可知
将 10 度分配给 6 个顶点，由以上的分析可知，只有下面 5 种分配方案：
① 1,1,1,1,1,5；
② 1,1,1,1,2,4；
③ 1,1,1,1,3,3；
④ 1,1,1,2,2,3；
⑤ 1,1,2,2,2,2.
显然不同的度数方案对应的无向树是非同构的. 同时还应特别注意，同一种方案可能对应不止 1 棵非同构的树. 在以上 5 种方案中，④对应 2 棵非同构的无向树，由 3 度顶点是否夹在两个 2 度顶点之间而定. 其余 4 种方案各对应 1 棵非同构的树. 所得 6 棵非同构的树如图 7.3 所示. 其中图 7.3(d) 与 (e) 都对应方案④；图 7.3(a)，(b)，(c) 分别对应方案①，②，③；图 7.3(f) 对应方案⑤.
例 7.4 画出度数列为 1,1,1,2,2,2,3 的所有非同构的 7 阶无向树.
解 画出所有 n 阶非同构的无向树不是易事，但当 n 较小时还是容易画出的. 本题是 7 阶非同构无向树度数分配方案中的一种，它有 3 个 2 度顶点，1 个 3 度顶点，3 度顶点与 1 个 2 度顶点相邻；与 2 个 2 度顶点相邻；与 3 个 2 度顶点都相邻，所得 3 棵树显然是非同构的，再无其他情况，所以共有 3 棵非同构的树，如图 7.4(a)，(b)，(c) 所示.
图 7.3 图 7.4
7.1.2 生成树
定义 7.2 设 G=\langle V,E\rangle 是无向连通图，T 是 G 的生成子图，并且 T 是树，则称 T 是 G 的生成树. G 在 T 中的边称为 T 的树枝. G 不在 T 中的边称为 T 的弦. T 的所有弦的集合的导出子图称为 T 的余树.
根据定理 7.1，n 阶 m 条边的连通图的生成树有 n-1 条树枝和 m-n+1 条弦.
在图 7.5 所示图中，图(b) 为图(a) 的一棵生成树，图(c) 为图(b) 的余树. 注意，余树虽然称做"树"，但它不一定连通，也不一定不含回路，因而余树不一定是树，更不是生成树.
图 7.5
定理 7.3 任何无向连通图 G 都存在生成树.
证明 若 G 中无回路，则 G 是树，于是 G 本身就是 G 的生成树. 若 G 中含回路 C，在 C 中任意删去一条边，不影响图的连通性. 若所得图中还有回路，就再在此回路中再删去一条边. 继续这一过程，直到所得图中无回路为止. 设最后的图为 T，则 T 是 G 的生成树.
推论 设 n 阶无向简单连通图 G 有 m 条边，则 m\geqslant n-1.
证明 由定理 7.3 可知，G 中存在生成树. 设生成树中有 m' 条树枝，m'=n-1. 因而，m\geqslant m'=n-1.
例 7.5 给出图 7.6(a) 中所示图的两棵非同构的生成树 T_1 和 T_2，并指出它们的树枝和弦.
图 7.6
解 在图 7.6(b) 和 (c) 中，实边所示的图都是图 7.6(a) 的生成树，设它们分别为 T_1 和 T_2，它们显然是非同构的. e_2,e_3,e_4,e_5 为 T_1 的树枝，e_1,e_6 为 T_1 的弦. e_1,e_2,e_4,e_5 为 T_2 的树枝，e_3,e_6 为 T_2 的弦.
例 7.6 设 G=\langle V,E\rangle 为无向连通图，试分析 G 中什么样的边不在 G 的任何生成树中？什么样的边在 G 的任何生成树中？
解 若 G 中有环，因为环为回路，所以环不能在任何生成树中. 若 G 中有桥，则桥在任何生成树中，否则得到的生成树是不连通的，这与树的定义相矛盾.
在实践中，有时不仅需要用图表示事物之间是否有某种关系，而且需要用数量来进一步表示这种关系. 例如，一张公路图，不仅要表示出两个城市之间是否有公路，而且要标出公路的长度. 为此，可以用顶点表示城市，用边表示两个城市之间有一条公路，并把这条公路的长度标在这条边的旁边. 这就是带权图.
定义 7.3 对图 G 的每条边 e 附加上一个实数 w(e)，称 w(e) 为边 e 的权. G 连同附加在各边的权称为带权图，常记作 G=\langle V,E,W\rangle.
定义 7.4 设无向连通带权图 G=\langle V,E,W\rangle，T 是 G 的一棵生成树. T 各边的权之和称为 T 的权，记作 W(T). G 的所有生成树中权最小的生成树称为 G 的最小生成树.
下面介绍求最小生成树的避圈法（Kruskal 算法）.
设 n 阶无向连通带权图 G=\langle V,E,W\rangle 有 m 条边. 不妨设 G 中没有环（若有环，将所有的环删去），将 m 条边按权从小到大顺序排列，设为 e_1,e_2,\cdots,e_m.
取 e_1 在 T 中，然后依次检查 e_2,e_3,\cdots,e_m. 若 e_i 与 T 中的边不能构成回路，则取 e_i 在 T 中，否则弃去 e_j.
例 7.7 某单位建设局域网需要铺设光缆，光缆连接的建筑物的位置、建筑物之间可以铺设光缆的线路及线路的长度（单位：m）如图 7.7 所示. 问：如何铺设才能使光缆的总长度最短？
解 根据题目的要求，应该按照图的一棵最小生成树铺设光缆. 用避圈法依次取边如下：(C,D)，(F,G)，(C,G)，(G,H)，(A,C)，(B,C)，(H,I)，(B,E). 求得图的最小生成树如图 7.8 所示. 光缆总长度为
当然，最小生成树不是唯一的. 如可以用 (A,D) 代替 (A,C)，用 (E,F) 代替 (B,E)，总长度不变.
图 7.7 图 7.8
解读：生成树的「树枝」和「弦」是一对互补的账：n 阶 m 边连通图的生成树一定取 n-1 条边（树枝），剩下的 m-n+1 条边就是弦，而余树只是弦的导出子图，名字带「树」却可能带圈、可能不连通，别被名字骗了。
避圈法的正确性直觉在于「贪心不吃亏」：按权从小到大逐条考虑，只要不闭合成圈就收下。因为任何一棵最小生成树都可以在不增加总权的前提下被调整成包含当前这条边，所以每次贪心都不会把最优解排除在外。带权图把「连接关系」升级为「连接代价」，最小生成树就是「用最低总代价把所有顶点连成一体」。