Prufer 序列

Prufer 序列的定义

$\rm Prufer$ 序列可以将一颗结点数为 $n$ 的有标号无根树用一个长度为 $n-2$值域为 $[1,n]$ 的数列唯一表示即有标号无根树和 $\rm Prufer$ 序列呈双射关系

具体来说有标号无根树的构建方式如下

  • 选择一个编号最小的叶子节点并将其删除
  • 将这个叶子节点所连接的点的编号加入 $\rm Prufer$ 序列中
  • 重复以上步骤 $n-2$直到树上只剩下 $2$ 个点

这是某一颗点数为 $n$ 的有标号无根树的 $\rm Prufer$ 序列的构造过程

Prufer

快速求解 Prufer 序列

由其过程显然有一个使用堆优化的 $\Theta(n\log n)$ 做法$\rm Prufer$ 序列其实可以线性构造

记录所有点的度数和一个指针 $p$ 指向编号最小的叶子节点进行以下操作

  • $p$ 指向的结点删除检查是否出现了新的叶结点
  • 如果产生了新的叶结点记其编号为 $x$$x>p$则不做任何操作否则将其删除并检查删除 $x$ 以后是否出现了新的叶结点重复这一步操作直到没有产生新的叶结点或新产生的结点编号大于 $p$
  • $p$ 自增直到遇见下一个叶结点为止
  • 重复以上操作直到结点数为 $2$ 可以得到这棵树的 $\rm Prufer$ 序列

可以发现在算法流程中每条边只在其连接的外层结点被删除时被遍历过一次并且 $p$ 单调递增树中的节点数单调递减所以每个点也只被遍历过一次

总时间复杂度 $\Theta(n)$

快速还原 Prufer 序列

显然还是有一个堆优化的 $\Theta(n\log n)$ 做法

从前到后枚举 $\rm Prufer$ 序列中的每一个数维护不在序列中的结点编号的最小值显然不在序列中的是叶子节点并且其最小值为最后一个加入的于是将其与当前枚举的序列中的数连边连边后若序列中已没有枚举的这个数那么将其踢出序列作为新的叶子结点

考虑以与之前构造 $\rm Prufer$ 序列相同的方法构造线性做法

记一个指针 $p$ 指向不在序列中的最小结点如果将其连向序列中枚举的位置并将枚举的位置删除序列中没有这个结点了那么如果被删除的结点比 $p$直接将其与现在序列中枚举的数连边后将其删除重复操作如果这个结点的值大于 $p$那么不用管它在后面它一定会被枚举到

显然这种算法的时间复杂度为 $\Theta(n)$

Prufer 序列的应用

Cayley 公式

完全图 $K_n$$n^{n-2}$ 颗生成树

证明方法很多其中最简单的应该是利用 $\rm Prufer$ 序列

考虑到任何一个长度为 $n-2$$\rm Prufer$ 序列唯一对应一颗大小为 $n$ 的有标号无根树于是考虑计算长度为 $n-2$$\rm Prufer$ 序列的数量又因为其值域为 $[1,n]$故总方案数为 $n^{n-2}$

限定度数的有标号无根树计数

求有 $n$ 个结点且第 $i$ 个结点的度数为 $d_i$ 的有标号无根树的数量

考虑到一个点的度数为其在 $\rm Prufer$ 序列中出现次数 $+1$于是对于一个度数为 $d_i$ 的点其在 $\rm Prufer$ 序列中的出现次数应为 $d_i-1$故存在这样的有标号无根树当且仅当 $\sum_{i=1}^n d_i-1=n-2$并且这样的树的数量为

$$\dbinom{n-2}{d_1-1,d_2-1,\cdots ,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots (d_n-1)!} $$