树的等价刻画 | Codeboy's Blog

形式陈述

设 $G=(V,E)$ 是非空有限简单无向图， $n=|V|$ 。以下条件等价：

第 5 条称为极小连通：极小针对边集的包含关系，表示没有边可再删除，并非在所有连通图中比较某个数值。第 6 条相应称为极大无圈。这两个“极”都必须连同前面的连通或无圈条件一起阅读。

由条件 1 出发，路与圈给出条件 2。连通性先保证两点之间有路；两条不同简单路会在分离和重合之间围出圈。反向地，若任意两点都有唯一路径，图自然连通；一旦有圈，圈上两点沿两个方向便有不同路径。

条件 2 立即推出条件 5。若删去边 $uv$ 后两端仍可相连，那条替代路径与 $uv$ 会给出第二条 $u$ – $v$ 路。反过来，满足条件 5 的图不可能含圈，因为删去圈上任一边后仍可沿圈其余部分绕行，连通性不会丢失。于是条件 1、2、5 互相等价。

树的边数可用叶归纳证明。 $n=1$ 时没有边；当 $n\ge2$ 时，最长路径端点给出一片叶子，删去叶及其唯一关联边后仍是树，因此边数随顶点数各减一。由此得到条件 $1\Rightarrow3$ 和 $1\Rightarrow4$ 。

若条件 3 成立，连通图含有生成树，而生成树已经使用 $n-1$ 条边； $G$ 没有剩余边可加，所以自身就是树。若条件 4 成立， $G$ 是森林；设它有 $c$ 个连通分量，逐分量应用树边数公式得

|E|=n-c.

结合 $|E|=n-1$ 可知 $c=1$ ，故 $G$ 连通。这完成条件 3、4 与树定义之间的转换。

最后，树中任意非边 $uv$ 的端点已有唯一 $u$ – $v$ 路，加入 $uv$ 正好闭合出一个圈，因此条件 $1\Rightarrow6$ 。若一个无圈图满足条件 6 却不连通，从两个不同分量各取一点并加边不会产生圈，矛盾；所以条件 6 也推出树。

直觉

这六种说法从不同方向捕捉同一个“没有冗余”的边界。路径刻画观察两点之间的路线数；边数刻画连接全部顶点所需的精确预算；极小连通考察删边，极大无圈考察加边。证明把这些视角接成闭环后，可以根据问题现有的信息选择最省力的入口。

边数 $n-1$ 正好落在平衡点，单独使用仍不足以判定树。连通性把边分散不足的可能排除，无圈性把边集中成局部环路的可能排除；任取其中一个结构条件与正确边数配合，才会锁定树。

例子与边界

路径图和星图的形状差别很大，但都满足六个条件。删去任何边时，它们都会分成两个分量；加入任意原本不存在的边时，新边与原唯一道路合成一个圈。这说明刻画约束的是连接机制，不是外观或度数分布。

三角形加一个孤立点有 $n=4$ 、 $|E|=3=n-1$ ，却既含圈又不连通。它同时展示条件 3 不能删去“连通”，条件 4 也不能删去“无圈”。仅核对边数会把两种缺陷恰好抵消。

若干彼此分离的非平凡树中，每条边都是桥，但整张图不连通，所以“每条边删后都会增加分量数”不能独自替代条件 5。相应地，一个已经含圈的完全图可能没有非边，使“加入任意非边”真空成立；条件 6 里的无圈假设同样不可省略。

单顶点图满足全部条件。第 5 条没有边可删，第 6 条没有非边可加，两者都真空为真；连通、无圈和 $|E|=|V|-1=0$ 则直接成立。

有限性是计数证明的一部分。无限树仍有唯一路径、极小连通和极大无圈等刻画，但基数等式 $|E|=|V|-1$ 失去有限整数的递减含义，最长路径也可能不存在。

推论与应用

要证明一张候选图是树，已知连通时只需证明边数为 $n-1$ ，已知无圈时也只需同一个计数；若图由构造过程生成，证明任意两点唯一路径往往更自然。等价定理的用途正在于替换证明义务，而非要求每次重新核验六项。

Kruskal 式构造始终保持无圈，直到母图中再无可加入的边。若所得森林仍有多个分量，连通母图必有一条边跨越其中两个分量，而加入这条边不会造圈，矛盾；所以结果是生成树。反过来，从连通图不断删除圈上的边会保持连通，最终由条件 5 停在一棵生成树。这两条路线分别体现“极大无圈”和“极小连通”。

树算法依赖不同刻画。根化与路径查询使用唯一路径，叶剥离和Prüfer 编码使用叶归纳，图拟阵把无圈边集作为独立集并把生成树作为极大独立集。选中合适的刻画，常能把全局论证压缩成一次局部交换。

参考资料

Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, §1.5.
Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001, §2.1.
Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, 2018 revision, Chapter 12.