图论中的树

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 树有七个定义，而它们说的是同一件事

请三个人给树下定义，你会得到三个答案。第一个人说它是没有环的连通图。第二个人说它是任意两个顶点之间恰有一条路径的图。第三个人说它是有 n - 1 条边的连通图。三个人都对，另外四种定义也同样正确，因为这些条件是等价的：满足其中任何一个条件的图，都满足全部条件。

这很少见，也正是树成为这门学科中最有用的特殊情形的原因。一个结构若有七种等价刻画，就有七种不同的方法来证明关于它的命题，实践中我们会挑选让证明最短的那一种。

先从标准定义讲起，也就是 Diestel 以及 Bondy 和 Murty 所采用的定义：

一棵树是连通的无环图。所有连通分量都是树的图称为森林。树中度为 1 的顶点称为叶子。

下文讨论的都是有限、简单、无向图，这是标准设定。无论如何，树都不可能有自环或平行边，因为两者都会构成环。

完整写出来，贯穿示例是

V = {1, 2, 3, 4, 5, 6, 7, 8}
E = { {1,3}, {2,3}, {3,4}, {4,5}, {5,6}, {5,7}, {7,8} }

度        1:1   2:1   3:3   4:2   5:3   6:1   7:2   8:1
n = 8     m = 7 = n - 1      度之和 = 14 = 2m      叶子：1, 2, 6, 8

2. 等价定理及其证明思路

下面是完整的结论。West、Bondy 和 Murty 以及 Diestel 的书中基本都以这种形式给出。它值得牢记，因为每一条都是一件工具。

定理。设图 G 有 n 个顶点，则以下命题等价：
(1) G 是树，即连通且无环。
(2) 在 G 中，任意两个顶点之间恰有一条路径。
(3) G 连通且有 n - 1 条边。
(4) G 无环且有 n - 1 条边。
(5) G 连通，且删除任意一条边都会使它不连通（极小连通）。
(6) G 无环，且添加任意一条边都会产生环（极大无环）。
(7) G 连通，且每条边都是桥。

证明不是一个单独的论证，而是一圈蕴含关系，每一步都很短。值得看清它的结构，因为它解释了为什么这些条件看起来如此不同，描述的却是同一个对象。

其中有两条值得特别强调，因为它们才是真正会用到的。

“连通且有 n - 1 条边”是代价最低的检验。统计边数只需 O(m) ，检查连通性只需 O(n + m)，因此无需寻找环，就能在线性时间内判断一个图是否为树。注意，任何一半单独都不够：三角形加上一个孤立顶点有 4 个顶点和 3 条边，却不是树；连通且有 4 条边的 4-环也不是。

“极小连通”与“极大无环”是从两个角度看同一个对象。树恰好处在边界上：它的边数少到连通性所允许的最低限度，又多到无环性所允许的最高限度。这就是为什么只要问题要求代价最低的连接结构，树就会出现，而这正是最小生成树问题。

七个条件在贯穿示例上全部成立，而且每一条都直接验证过：它连通、无环、8 个顶点有 7 条边、28 对顶点中每一对之间恰有一条路径、7 条边中每一条都是桥，21 条不存在的边中任意一条被加入都会闭合成环。

3. 叶子引理

一个小结论支撑着这门学科中大部分的归纳证明。

叶子引理。每棵至少有两个顶点的有限树都至少有两片叶子。

这个证明很受欢迎，因为它除了定义之外什么都不用。取树中的一条最长路径 P ，设它从 u 到 v。由于树是有限的，这样的路径一定存在。现在考虑 u。如果 u 有一个邻居 w 不在 P上，那么 P 就可以沿这条边延长，与它是最长路径矛盾。如果 u 还有第二个邻居位于路径 on P上，就会形成一个环，与无环性矛盾。因此 u 恰有一个邻居，是一片叶子；同样的论证也适用于 v。

由此立刻得到两个推论，而且两者都经常用到：

• 对树做归纳时，总有一个基础情形可以剥去。从树上删去一片叶子，剩下的仍是一棵少一个顶点的树。这一个动作是以下内容的引擎：证明树有 n - 1 条边，第 7 节中的 Prüfer 编码，以及第 10 节中的求中心算法。
• 这个界是紧的。路径恰有两片叶子，所以一般情况下“至少两片”无法再改进。另一个极端是星图 K1,n-1 ，它有 n - 1 片叶子。

贯穿示例有四片叶子：1、2、6 和 8，远多于保证的两片。调试树相关代码时，这是一个有用的合理性检查：如果你的结构自称是树，却报告少于两片叶子，那就一定出了问题，通常的罪魁祸首是意外形成的环。

叶子引理恰恰也是在无限图上失效的地方。单向无限路径只有一片叶子，双向无限路径则一片也没有，这是有限性作用最清晰的例证之一，详见有限图与无限图指南。

4. Forests, and counting components for free

所谓森林，是指无环图，连通与否均可。森林的每个连通分量都是一棵树，由此得到一个值得熟记的计数恒等式：

一个有 n 个顶点、 k 个连通分量的森林恰有 n - k 条边。

证明只需一行：每个连通分量都是树，所以一个有 ni 个顶点的分量贡献 ni - 1 条边，对全部 k 个分量求和得到 n - k。令 k = 1 ，就回到了树的情形。

反过来读，这个恒等式就从一个事实变成了一件工具：

k = n - m        森林的连通分量数，
                 仅由它的规模算出，无需任何遍历

这确实有用。如果你知道一个图是无环的，只要数一数顶点和边，就能知道它分成几块，无需运行任何搜索。这也是标准并查集结构不变量背后的恒等式：每次成功的合并都会融合两个分量并加入一条边，因此运行中的计数 n - (已完成的合并次数) 始终等于连通分量数。

需要提醒一点：这个恒等式以无环为前提。对一般的图，总有 m ≥ n - k ，且等号恰好在图为森林时成立，因此边数多于 n - k 的图必然含有环。这个不等式是不必找出环就能证明图中有环的最快方法：若 m ≥ n，则图中某处必有环。

5. 生成树

所谓生成树，是指连通图 G 的一个子图，它是一棵树，并且包含 G的所有顶点。它是让图保持连通的最小骨架。

每个有限连通图都有生成树，其构造性证明值得了解，因为它本身也是一个算法：只要还有环，就删去环上的一条边。删去环上的边不会破坏连通性，因为环的其余部分仍连接着它的两个端点；而每一步都会去掉一条边，所以过程必然终止。剩下的图连通且无环。等价而且更实用的做法是：任何 BFS 或 DFS 遍历所产生的发现边构成的树，本身就是一棵生成树，用时 O(n + m)。

关于生成树，有三个事实会反复出现：

• 每棵生成树恰有 n - 1 条边，无论原图长什么样。因此在无权图上，所有生成树都一样好，最小生成树问题只有在边带有权重时才变得有意义。
• 生成树的数量可能极其庞大。完全图 Kn 有 nn-2 棵生成树，这又是从生成树角度看到的 Cayley 公式。
• 一棵树唯一的生成树就是它自己。说出来显而易见，但它是测试代码时很有用的退化情形：任何生成树计数程序在树上都必须恰好返回 1，第 8 节中对贯穿示例所做的矩阵树计算证实了这一点。

对于无限图，“每个连通图都有生成树”这一命题仍然成立，但它需要选择公理，而且实际上与选择公理等价。这条边界的讨论见有限图与无限图指南。

6. 带标号树的计数：Cayley 公式

在一个固定的、有 n 个带标号顶点的集合上，能构造出多少棵不同的树？答案是组合数学中被引用最多的结论之一，由 Arthur Cayley 于 1889 年发表。

Cayley 公式。有 n 个顶点的带标号树的数量是 nn-2。

最初几个值增长得很快，值得一看，因为最小的几个可以手工验证：

上表中 n = 4 和 n = 5 的数值并非引自书本，而是通过枚举全部 n - 1 条边的子集（从 C(n, 2) 条候选边中选取）并保留其中连通的那些得到的，结果恰好是 16 和 125。

关于“带标号”的含义要说一句，因为这个区别正是第 9 节的全部主题。Cayley 计数的是顶点彼此可区分的树，因此路径 1 - 2 - 3 和路径 2 - 1 - 3 虽然形状相同，却是不同的树。去掉标号，三个顶点上就只有一种树的形状。

这个公式有好几种证明，包括对有根森林的双重计数论证，以及借助矩阵树定理的行列式论证。最有启发性的是一个双射，而且它短到可以完整演示一遍。

7. Prüfer 双射，完整演示

Heinz Prüfer 在 1918 年给出了 Cayley 公式的一个证明：他在有 n 个顶点的带标号树与长度为 n - 2 、取值于 {1, …, n}的序列之间构造了一个明确的双射。由于这样的序列恰有 nn-2 个，公式随即得证。

编码。只要剩下的顶点多于两个，就找出标号最小的叶子，记下它唯一邻居的标号，然后删去这片叶子。剩下两个顶点时停止。在贯穿示例上，逐步过程如下：

删去叶子 1  →  记下 3      剩余：2,3,4,5,6,7,8
删去叶子 2  →  记下 3      剩余：3,4,5,6,7,8
删去叶子 3  →  记下 4      剩余：4,5,6,7,8
删去叶子 4  →  记下 5      剩余：5,6,7,8
删去叶子 6  →  记下 5      剩余：5,7,8
删去叶子 5  →  记下 7      剩余：7,8

Prüfer 序列：(3, 3, 4, 5, 5, 7)        长度 6 = n - 2

解码。逆过程把同样的思路倒过来用。给每个顶点一个计数器，初值为一加上它在序列中出现的次数，这就是它的度。然后反复取计数器为 1 且尚未使用的最小顶点，把它与序列中剩下的第一个元素相连，并把两者的计数器各减一。序列用完后，把计数器仍为 1 的两个顶点相连。对 (3, 3, 4, 5, 5, 7) 执行这一过程，恰好还原出原来的边集，这正是这个对应是双射而不仅仅是摘要的原因。

这种编码最有用的性质是：

顶点 v 在 Prüfer 序列中恰好出现 deg(v) - 1 次。特别地，叶子恰好就是从不出现的那些标号。

在贯穿示例上验证一下。顶点 3 的度为 3，出现两次；顶点 5 的度为 3，出现两次；顶点 4 和 7 的度为 2，各出现一次；叶子 1、2、6、8 则完全不出现。这种对应把关于度序列的问题转化为关于字符串中符号频率的问题，这就是 Prüfer 序列成为计数给定度数的树、以及均匀随机生成带标号树的标准工具的原因：随机生成一个长度为 n - 2 的序列，再对它解码即可。

8. 矩阵树定理

Cayley 公式计数的是完全图的生成树。Kirchhoff 的矩阵树定理比它早四十多年，源于他 1847 年对电路网络的研究，能计数任意图的生成树。

构建拉普拉斯矩阵 L = D - A，其中 D 是度构成的对角矩阵， A 是邻接矩阵。于是：

矩阵树定理。删去 L的任意一行及对应的一列。剩下的 (n-1) × (n-1) 矩阵的行列式就是该图生成树的数量。删去哪一行哪一列都没有关系。

下面三个计算让这个定理变得具体，而且三个都是实际算出来的，而非引用：

环的情形最适合用来建立直觉：有 k 个顶点的环恰有 k 棵生成树，你选择删去哪条边就对应哪一棵。这个定理也解释了多重图指南中的一个说法：平行边确实会改变生成树的数量，因为它们在拉普拉斯矩阵中表现为非对角线上的重数，所以由两条平行边相连的两个顶点有两棵生成树，而不是一棵。

9. 无标号树：一个难得多的问题

Cayley 公式之所以简洁，是因为标号让树很容易区分。如果改问在同构意义下有多少棵树，也就是有多少种不同的形状，问题就变得真正困难了。

这两列讲的是完全不同的故事。带标号的数量有一行的闭式公式；无标号的数量则没有。对于有 n 个顶点的树在同构意义下的数量，目前不知道任何公式，只有生成函数方法，以及 Richard Otter 于 1948 年给出的渐近结果，它表明该数量的增长速度为 C · αn n-5/2 ，其中常数由数值计算得出。

造成这种差距的原因是对称性。把带标号的数量除以 n! 只有在每棵树的自同构群都平凡时才正确，而大多数树并非如此：路径可以翻转，星图的叶子可以任意置换，每一种对称都会让多个标号方式合并成同一种形状。计数对称群作用下的轨道恰恰是难点所在，这就是该问题需要 Pólya 计数理论而不是一个公式的原因。

对程序员来说，这一区别的实际形式是树同构判定：判断两棵树是否形状相同。与一般的图同构不同，它可以在线性时间内解决：从叶子开始自底向上对每棵子树做规范哈希，然后在中心处比较结果。一般问题困难而树的情形容易，这再次体现了贯穿全文的规律。

10. 中心、半径与直径

一个顶点的离心率是它到其他任意顶点的最大距离。图的半径是最小的离心率，直径是最大的离心率，而中心是离心率等于半径的顶点集合。对树而言，这些概念表现得格外简洁，这是 Camille Jordan 在 1869 年证明的。

Jordan 定理。树的中心要么是一个顶点，要么是两个相邻的顶点。

绝不会是三个，也绝不会是两个不相邻的顶点。与环比较一下：环上所有顶点都在中心，树的情形之简洁便一目了然。

这个证明同时也是一个算法。反复同时删去当前所有的叶子。每一轮都使剩余每个顶点的离心率恰好减 1，因此离心率最小的顶点被保留下来，过程在剩下一个或两个顶点时停止。在贯穿示例上：

初始                        1 2 3 4 5 6 7 8
删去叶子 1, 2, 6, 8   →   剩余  3 4 5 7
删去叶子 3, 7         →   剩余  4 5      ← 中心

离心率   1:5  2:5  3:4  4:3  5:3  6:4  7:4  8:5
半径 3     直径 5     中心 {4, 5}，两者相邻，正如 Jordan 定理所要求

剥叶子的结果已与直接计算全部八个离心率的结果对照过，两者完全一致：离心率最小的顶点恰好是 4 和 5。该算法的运行时间为 O(n)，这就是它成为把树“从中间”定根的标准方法的原因，例如在同构判定中进行规范哈希之前。

在树中还有一个值得记住的恒等式：

半径 = ⌈直径 / 2⌉        此处：3 = ⌈5 / 2⌉

它源于这样一个事实：树的直径由一条唯一的路径实现，而中心就位于这条路径的中点。在一般的图中，只有较弱的不等式 radius ≤ diameter ≤ 2 · radius 成立。

11. 树中的距离与两次 BFS 技巧

由于任意两个顶点之间恰有一条路径，树中的距离比任何其他图类都简单。没有什么需要优化：唯一的路径就是最短路径，因此找到它既不需要权重，也不需要优先队列或 Dijkstra 算法。

这种唯一性带来了一个优雅且广泛使用的求直径算法：

两次 BFS。从任意顶点出发做一次广度优先搜索，设 a 是找到的一个最远顶点。再从 a 出发做第二次搜索，设 b 是离它最远的一个顶点。那么从 a 到 b 的路径就是一条直径，而 dist(a, b) 就是直径的长度。

两次线性扫描，无需权重，也没有任何花招。在贯穿示例上，从顶点 1 出发，搜索到的最远顶点是 8；再从 8 出发做第二次搜索，得到距离为 5 的顶点 1，这与把全部离心率取最大值算出的真实直径一致。

值得说明它为什么有效，因为这个技巧在一般图上会失效，却常被照搬过去。关键论断是：从任意起点出发找到的最远顶点，总是某条直径的端点。在树中这是成立的，因为路径的唯一性迫使最远顶点位于最长路径的末端；在有环的图中，这个论断根本不成立，两次扫描的方法可能会低估直径。在一般图上计算直径需要求出所有顶点对之间的距离。

还有一些关于距离的事实在树中成立，而在一般情况下其他地方都不成立：

• 删去任意一条边都会把树恰好分成两个连通分量，因为每条边都是桥。这正是树上的分治（例如重心分解）如此干净利落的原因。
• 两个顶点之间的路径可以仅凭父指针重建，只要树已定根，所需时间与路径长度成正比，这是最近公共祖先相关技术的基础。
• 距离满足四点条件，这是一个度量恒等式，恰好刻画了来自树的距离矩阵，也是从遗传距离数据重建系统发育树的基础。

12. 自由树、有根树与有序树

到目前为止讨论的都是自由树：没有特殊顶点、顶点的邻居之间也没有顺序的连通无环图。计算机科学几乎总是处理结构更多的对象，Knuth 的 The Art of Computer Programming 对这三个层次做了仔细区分，因为每个层次上的计数都不相同。

定根并不改变图，改变的是问题。底层的边集完全相同；根带来的是方向，以及随之而来的父节点、子节点、祖先、后代、深度和高度等一整套术语，配套的有根树指南连同标准遍历方法对此做了详细讲解。

计数上的差别最清楚地表明它们确实是不同的对象。有 n 个节点的有序二叉树由卡特兰数计数， n = 0 到 5 时依次为 1, 1, 2, 5, 14, 42，而相同顶点数的自由树要少得多。每多施加一种结构，不同对象的数量就会成倍增加。

由第 10 节可以得到一条实用建议：当算法需要一个根而又没有给定时，在中心定根通常是正确的默认选择。这样能使高度最小，而高度决定了在树上运行的任何递归的深度上界。

13. 树在计算机科学中的应用

树是计算机科学中最常见的、真正属于图的结构。值得区分两种情况：一种是树本身就是数据，另一种是树作为算法输出的证书。

作为数据的树。层次结构才是重点：

• 文件系统。目录和文件构成一棵有根树，至少在不允许符号链接和硬链接时如此；一旦允许，它就变成一般的图，唯一路径的保证随之消失。这正是链接循环会让简单的目录遍历崩溃的原因。
• 语法分析树与抽象语法树。每个编译器前端都会产生这样的树。正因为是树，递归求值才有良基性：一个子表达式不可能包含它自己。
• DOM。 HTML 文档是一棵有序有根树，CSS 选择器就是对其中祖先关系和兄弟关系的查询。
• 搜索树、字典树与堆。二叉搜索树、B 树和字典树都是通过约束形状来限制深度的树，而深度正是有根树的高度。
• 决策树。每个内部节点检验一个特征，每片叶子给出一个预测；从根到叶子的唯一路径就是对模型输出的解释。

作为证书的树。这里，树是算法的输出，编码了一个证明：

• BFS 树与 DFS 树。对连通图的任何遍历都会产生一棵由发现边构成的生成树。BFS 树还能证明无权图中的最短距离，而 DFS 树的回边则让我们能够检测环和找出桥。
• 最短路径树。 Dijkstra 算法会产生这样一棵树：一棵生成树，其中从源点到每个顶点的路径都是最短路径。注意，它一般并不是最小生成树，把两者混为一谈是经典错误。
• 最小生成树。 Kruskal、Prim 和 Borůvka 算法各自证明了代价最低的连接子图，详见最小生成树指南。
• 并查集森林。不相交集合结构字面上就是一片森林，而路径压缩是一种把其中的树压平、使高度几乎保持常数的操作。
• Merkle 树。版本控制系统和分布式系统中的哈希树利用唯一路径的性质，使单片叶子的改动沿着恰好一条路径向上传播到根，从而让验证只需对数时间。

有一点需要澄清，因为术语容易误导：Git 的提交历史并不是树。合并提交有两个父提交，所以历史是一个有向无环图。Git 的“tree”对象则完全是另一回事，指的是目录快照。DAG 与树的区别恰恰在于树中任意两个节点之间只有唯一的路径，而一次合并就会破坏这一点。

14. 常见错误

• 只检查定义的一半。只要求“连通”会允许环；只要求“有 n - 1 条边”会允许三角形加一个孤立顶点。你需要第 2 节定理中的一对条件，而连通加上 n - 1 条边是代价最低的组合。
• 以为最短路径树就是最小生成树。两者优化的目标不同：一个使从源点出发的每个距离最小，另一个使边的总权重最小。它们经常不同。
• 在有环的图上使用两次 BFS 求直径。它只在树上有效，因为唯一路径的性质使最远顶点成为直径的端点。在一般图上，它可能在毫无提示的情况下低估直径。
• 混淆带标号计数与无标号计数。 5 个顶点的带标号树有 125 棵，而形状只有 3 种。除以 n! 并不能从一个得到另一个，因为树具有对称性。
• 忘记定根在结构上什么也没改变。根增加的是一个问题，而不是一条边。底层的自由树不变，因此为自由树证明的任何结构性事实依然成立。
• 期望叶子引理在无限树上成立。双向无限路径无环且连通，却一片叶子也没有。
• 把 DAG 当作树。 DAG 中两个节点之间可以有多条路径，树则不行。任何依赖路径唯一性的算法，包括按节点做键的朴素记忆化，都会出错。
• 构建出含有环的“树”。运行时最快的检查是边数：如果一棵所谓有 n 个顶点的树不是恰好有 n - 1 条边，就停下来找 bug。

15. 术语表

17. 参考文献

以上定义、定理和归属的出处，以及系统阐述这些内容的标准教材，按时间顺序排列。

1. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12)，497 至 508 页。矩阵树定理。
2. Jordan, C. (1869). "Sur les assemblages de lignes." Journal für die reine und angewandte Mathematik 70，185 至 190 页。树的中心是一个顶点或两个相邻的顶点。
3. Cayley, A. (1889). "A Theorem on Trees." Quarterly Journal of Pure and Applied Mathematics 23，376 至 378 页。
4. Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen." Archiv der Mathematik und Physik 27，142 至 144 页。第 7 节中的双射。
5. Borůvka, O. (1926). "O jistém problému minimálním." Práce Moravské Přírodovědecké Společnosti 3，37 至 58 页。
6. König, D. (1936). Theorie der endlichen und unendlichen Graphen. 莱比锡：Akademische Verlagsgesellschaft。
7. Otter, R. (1948). "The Number of Trees." Annals of Mathematics 49(3)，583 至 599 页。无标号树的渐近计数。
8. Kruskal, J. B. (1956). "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem." Proceedings of the American Mathematical Society 7(1)，48 至 50 页。
9. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal 36(6)，1389 至 1401 页。
10. Harary, F. (1969). Graph Theory. 马萨诸塞州雷丁：Addison-Wesley。
11. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms，第 3 版，第 2.3 节。马萨诸塞州雷丁：Addison-Wesley。自由树、有根树与有序树的区分。
12. West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。第 2 章系统讲解树与距离。
13. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。伦敦：Springer。
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版。马萨诸塞州剑桥：MIT Press。
15. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。第 1.5 节讲解树与森林。