生成树计数：Prüfer 序列与矩阵树定理

生成树和计数 #

本节的有标号树以 $[n]=\{1,\ldots,n\}$ 为固定顶点集。先讨论 $n\geqslant 2$ ； $n=1$ 时只有一棵单顶点树，单独处理。

定理凯莱公式 Cayley

$n\geqslant 2$ 个有标号顶点的树一共有 $n^{n-2}$ 棵，也就是完全图 $K_n$ 的生成树数量。

Prüfer 编码：由树生成序列 #

输入是一棵顶点集为 $[n]$ 的树，输出是长度为 $n-2$ 的序列 $(a_1,\ldots,a_{n-2})$ 。

将当前树初始化为输入树，序列初始化为空。
在当前树中选取编号最小的叶子 $v$ ，把它唯一的邻点编号 $u$ 追加到序列末尾。
删除叶子 $v$ 及边 $vu$ ，在剩余的树上重复第 2 步，直到只剩两个顶点。
返回已经记录的 $n-2$ 个编号。最后两个顶点之间的边不再产生序列项。

删除叶子后仍是树，因此每步都能继续进行。当 $n=2$ 时不执行删除，编码就是空序列。

逆映射：由序列重建树 #

输入 $n\geqslant 2$ 和任意序列 $(a_1,\ldots,a_{n-2})\in[n]^{n-2}$ 。以下“剩余序列”始终指尚未读取的后缀，不是最初的整条序列。

令剩余顶点集 $S=[n]$ ，边集为空，并统计各编号在剩余序列中的出现次数 $c(v)$ 。
读取当前首项 $a_i$ ，选取 $S$ 中满足 $c(v)=0$ 的最小编号 $v$ ，添加无向边 $\{v,a_i\}$ 。
从 $S$ 中移除 $v$ ，消费序列首项 $a_i$ ，并将 $c(a_i)$ 减一；其余计数不变。重复第 2 步直到序列为空。
此时 $S$ 恰剩两个顶点，将它们连接，得到所求树。

若还剩 $m$ 个序列项，则 $S$ 有 $m+2$ 个顶点，至少两个编号不在剩余序列中出现，因此第 2 步总能选到 $v$ ，且 $v\ne a_i$ 。每次被移除的顶点都接到仍保留的顶点上；倒过来看，是从最后一条边开始不断添加叶子，所以结果连通且无环。

为何编码与解码互逆

对树的编码过程，任意顶点 $v$ 被记录的次数恰为 $\deg_T(v)-1$ ：在它被删除或成为最后两个顶点之前，每删去一条通向它的叶边就记录一次它；最后剩下的一条关联边不再记录它。

同样的关系在每棵剩余树和对应的剩余序列之间仍成立。因此，剩余序列中未出现的顶点恰为剩余树的叶子，解码时选择的最小编号正是编码时删除的最小叶子。记录的首项就是其唯一邻点，两种操作逐步相互抵消。

反向构造所得树也满足该度数关系，故任意合法序列都能被重新编码为自身。由此建立有标号树与 $[n]^{n-2}$ 的双射，得到 Cayley 公式。

例如，边集为 $\{\{1,3\},\{2,3\},\{3,4\},\{4,5\}\}$ 的树编码如下，逆映射按相同行顺序重建这些边。

步骤	删除的最小叶子	记录的邻点	当前已记录序列
1	1	3	`(3)`
2	2	3	`(3,3)`
3	3	4	`(3,3,4)`
结束	剩余 4、5	不再记录	`(3,3,4)`

Prüfer 双射还可参阅南京大学组合数学课程的 Cayley 公式讲义。

指定度数的树计数 #

推论

设 $n\geqslant 2$ ，正整数列 $d_1,\ldots,d_n$ 满足 $\sum_{i=1}^n d_i=2n-2$ ，则顶点 $i$ 的度数恰为 $d_i$ 的有标号树共有

\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}

棵。

因为编号 $i$ 必须在 Prüfer 序列中恰出现 $d_i-1$ 次，问题等价于排列这个长度为 $n-2$ 的多重集。若某个 $d_i<1$ 或度数和不等于 $2n-2$ ，则在 $n\geqslant 2$ 时没有这样的树；单顶点树的度为 $0$ ，不代入上述阶乘公式。

拉普拉斯矩阵与矩阵树定理 #

定义

设 $G$ 是有限无向无自环图，允许平行边，顶点为 $v_1,\ldots,v_n$ 。令 $A=(a_{ij})$ 为邻接矩阵，其中 $a_{ij}$ 是连接 $v_i,v_j$ 的边数； $D=\operatorname{diag}(\deg v_1,\ldots,\deg v_n)$ 是度数矩阵。图的拉普拉斯矩阵为

L(G)=D-A.

定理矩阵树

对上述 $n\geqslant 2$ 的图，记 $\tau(G)$ 为生成树数。任取 $r\in\{1,\ldots,n\}$ ，从 $L(G)$ 中同时删去第 $r$ 行与第 $r$ 列，得到主子矩阵 $L^{(r)}$ ，则

\tau(G)=\det L^{(r)}.

不论选哪一个 $r$ ，结果都相同。平行边按不同边计数；非连通图的生成树数与这些行列式都为 $0$ 。

先忽略自环再构造上述矩阵，因为自环不能属于生成树。这里求的是删去一行一列后的行列式，不是 $\det L$ ； $L$ 的每行之和为 $0$ ，所以 $\det L=0$ 。对 $n=1$ ，约定空矩阵的行列式为 $1$ ，与单顶点树的计数一致。

证明思路

任意给边定向，写出顶点与边的带符号关联矩阵 $B$ ；每列在两端各取 $1,-1$ ，便有 $L=BB^{\mathsf T}$ 。删除第 $r$ 行得到 $B_r$ ，从而 $L^{(r)}=B_rB_r^{\mathsf T}$ 。Cauchy–Binet 公式给出

\det L^{(r)}=\sum_{\substack{S\subseteq E\\|S|=n-1}}\bigl(\det B_r[:,S]\bigr)^2.

若 $S$ 不是生成树，其列向量线性相关，贡献为 $0$ ；若 $S$ 是生成树，沿叶子展开行列式可得值为 $\pm1$ ，平方后贡献为 $1$ 。因此右侧恰好数出所有生成树。

上述定理及关联矩阵证明见 MIT 18.314《The Matrix Tree Theorem》定理 1.8。

例如三角形 $K_3$ 的拉普拉斯矩阵及一个主子矩阵为

L=\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix},\qquad L^{(3)}=\begin{pmatrix}2&-1\\-1&2\end{pmatrix}.

于是 $\tau(K_3)=4-1=3$ ，与删去三角形任意一条边所得的三棵生成树一致。