# Prüfer 序列

# 简介

在图论、组合数学中， 一棵有标号无根树的 Prüfer 序列是一个唯一的序列， 且每个 Prüfer 序列与唯一一棵树对应. 一个含有 $n$ 个节点的有标号无根树的 Prüfer 序列长度为 $n - 2$.

# 将无根树转化为 Prüfer 序列

总体的思路是迭代删点，直到原图中只剩下两个点. 对于一棵树 $T$, 我们每次找到树中标号最小的叶子结点， 将这个叶子结点以及与它相邻的边删去， 将与叶子结点相连的点加入数列中. 重复上一步，直到原图中只剩下两个点.

# 将 Prüfer 序列转化为无根树

对于长度为 $n-2$ 的 Prüfer 序列， 首先建立一个含有 $n$ 个孤立的点的图. 设集合 $V = \{1,2,\dots,n\}$， 每次找到集合 $V$ 中最小的未在序列中出现的元素， 将该元素与序列的第一项连边， 然后从集合中删去那个元素， 删去序列的第一项. 重复上述操作，直到序列为空， 此时集合中仅剩两个元素，将这两个元素连边.

# 性质

• 一个长度为 $n-2$ 的序列与一棵有 $n$ 个节点的有标号无根树唯一对应
• 某个节点标号在 Prüfer 序列中出现的次数 + 1 = 该节点在原无根树中的度数

# Cayley 公式

一个完全图 $K_n$ 有 $n^{n-2}$ 个生成树， 亦即 $n$ 个节点的带标号的无根树有 $n^{n-2}$ 个.

# 一些应用

如果限定生成树的结点 $i$ 的度数为 $d_i$， 那么完全图 $K_n$ 符合条件的生成树的个数为多项式系数

$\begin{pmatrix} n - 2 \\ d_1 - 1, d_2 - 1, \dots, d_n - 1 \end{pmatrix} = \frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!}$