如何优美地数树 ~ 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}\)。