树

从树中去掉任意一条边都会使其不连通,添加任意一条边都会产生一个环——树恰好拥有连接一切所需的边数,不多不少。这三个条件分别从不同角度锁定了这种"恰到好处"的结构。

我们证明 (i) 连通且无环 $\implies$ (ii) 连通且有 $n-1$ 条边 $\implies$ (iii) 无环且有 $n-1$ 条边 $\implies$ (i),从而把三者串成一个环。

**(i)$\implies$(ii)**,对 $n$ 归纳。基础情形 $n=1$ 显然:单个顶点有 $0 = n-1$ 条边。归纳步骤:取一个 $n\ge2$ 个顶点的连通无环图 $T$。由于 $T$ 有限且无环,它必含一个叶子 $v$(度为 $1$ 的顶点):否则每个顶点的度都 $\ge 2$,从任意起点出发沿边前进且不立即折返,最终必会重访某个顶点,从而产生环。删去 $v$ 及其唯一关联边,剩下的图 $T'$ 有 $n-1$ 个顶点,依然连通(没有其他顶点依赖 $v$ 来保持连通)且依然无环(无环图的子图仍无环)。由归纳假设,$T'$ 有 $(n-1)-1$ 条边,故 $T$ 有 $(n-1)-1+1 = n-1$ 条边。

**(ii)$\implies$(iii)**。设 $T$ 连通且有 $n-1$ 条边。若 $T$ 含有一个环,删去该环上的一条边后图仍连通(被删边的两端点仍由环的其余部分相连),这就得到一个在 $n$ 个顶点上只有 $n-2$ 条边的连通图。但任何 $n$ 个顶点上的连通图都至少需要 $n-1$ 条边(除第一个顶点外,每个新顶点都至少需要一条新边才能到达),所以 $n-2$ 条边不可能让 $n$ 个顶点连通——矛盾。故 $T$ 不含环,即无环。

**(iii)$\implies$(i)**。设 $T$ 无环且有 $n-1$ 条边,并设其有 $c$ 个连通分量。每个分量本身连通且无环,于是对每个分量分别应用已证明的 (i)$\implies$(ii) 方向,一个有 $n_i$ 个顶点的分量就有 $n_i - 1$ 条边。对所有分量求和,总边数为 $\sum_i (n_i - 1) = n - c$。已知总数为 $n-1$,故 $n - c = n - 1$,于是 $c=1$:$T$ 连通。

它回答了一个纯组合问题——把 $n$ 个可区分的点连成一个树形网络共有多少种不同方式——给出了一个出人意料简洁的封闭公式,而用来证明它的编码技巧(Prüfer序列)把"数树的个数"变成了"数序列的个数",一个容易得多的问题。

固定顶点集为 $\{1,\dots,n\}$,对 $n\ge2$ 定义带标号树 $T$ 的Prüfer序列:反复找到标号最小的叶子,记下其唯一邻居的标号,然后删去该叶子;当只剩下 $2$ 个顶点时停止。这样记录了 $n-2$ 个标号(每删除一次记一个,因为从 $n$ 个顶点开始、停在 $2$ 个),所以每棵带标号树都产生 $\{1,\dots,n\}^{n-2}$ 中的一个序列。

这样的序列恰有 $n^{n-2}$ 个,因为 $n-2$ 个位置中的每一个都可独立取 $n$ 个标号中的任意一个。剩下要证明这个编码是一个双射,使带标号树与这些序列一一对应。

关键事实是:在Prüfer序列中,标号 $i$ 恰好出现 $\deg(i)-1$ 次:每当 $i$ 的某个邻居作为叶子被删除时,$i$ 就被记录一次,而 $i$ 本身只有在除一条关联边外全部消失后才会被删除(不产生记录)。特别地,从未出现在序列中的标号恰好就是最初的叶子。这使我们能够解码:给定序列 $(a_1,\dots,a_{n-2})$,反复取出尚未作为剩余序列条目出现、也尚未被连接的最小标号,将其与剩余序列的第一个条目用一条边相连,把该标号从后续候选中去除,并从序列中删去该条目;当全部 $n-2$ 个条目用完后,把剩下的 $2$ 个标号用最后一条边相连。

这个解码过程按剩余顶点数进行归纳,精确地逐步逆转编码过程——每一步都识别出与编码器本应记录的相同的最小标号叶子及其邻居。因此编码与解码互为逆过程,给出了 $n$ 个顶点上带标号树与 $\{1,\dots,n\}^{n-2}$ 中序列之间的双射。由于这样的序列恰有 $n^{n-2}$ 个,$n$ 个顶点上的带标号树也恰有 $n^{n-2}$ 棵。