如何优美地数树 ~ Prüfer 序列学习笔记

Prüfer 序列

首先定义无向树的 Prüfer 序列：

对于一颗无向树，考虑按照下列步骤建立 Prüfer 序列：

最终得到的序列就是该无向树的 Prüfer 序列。

用堆暴力构造是 $O(n\log n)$ 的，有一个线性构造办法：

记录指针 $p$ 和每个点的度数 $\deg_i$ ，按照以下步骤建立序列：

若 $p$ 为叶子节点，删除节点 $p$ （不改变指针 $p$ 的位置）；
判断是否产生新的叶子节点。若产生，则判断新叶子节点编号 $q$ 与 $p$ 的大小关系。若 $q<p$ ，则立即删除 $q$ ，重复步骤 $2$ ；否则不进行操作；
自增 $p$ 直到变为步骤 $1$ 。

正确性是显然的，时间复杂度 $O(n)$ 。

根据 Prüfer 序列可以唯一地重建树。方法与建立类似。

Prüfer 序列实际上与无向树构成了双射关系，用处就是数树。

性质：结点 $i$ 在序列中出现的次数是 $\deg_i-1$ 。

Cayley 公式

Cayley 公式： $n$ 个标号点形成的树的数量为 $n^{n-2}$ 。

等价于：完全图 $K_n$ 的生成树个数为 $n^{n-2}$ 。

用 Prüfer 序列可以方便地证明 Cayley 公式.

证明：任意一个长度为 $n-2$ 的，值域为 $[1,n]$ 的 Prüfer 序列都是原图的一棵生成树。证毕。

广义 Cayley 公式： $n$ 个标号点形成一个有 $k$ 颗树的森林，使给定的 $k$ 个点中任两点不属于同一棵树的方案数为 $k\cdot n^{n-k-1}$ 。

证明：不妨钦定给定的 $k$ 个点分别为 $k$ 颗树的根。我们建立一个虚根 $I$ ，钦定其编号为 $n+1$ ，并分别钦定 $k$ 个点编号为 $n-k+1\sim n$ 。

由于 Prüfer 序列每次删叶子节点，因此这 $k$ 个点一定是最后被删除的，并且加入序列的数一定是 $n+1$ 。也就是说，Prüfer 序列最后 $k-1$ 个点一定是 $n+1$ 。

编号为 $n-k-2$ 的节点，其父亲一定只能是这 $k$ 个点。剩余的 $n-k-1$ 个点，其父亲可以是 $[1,n]$ 中任意节点。

因此最终的方案数就是 $k\cdot n^{n-k-1}$ 。