prufer数列

发表于 2020-07-02 分类于总结

prufer数列的一些基础。

prufer数列是一棵无根树所生成的数列，对于一棵有 $n$ 个点的树，它的prufer数列长度为 $n-2$。

转换

我们定义一棵无根树中度数为 $1$ 的点是叶子。

将以下操作重复 $n-2$ 遍：

将树中编号最小的叶子拎出来，在数列末尾写上与这个叶子相连的点，然后删除这个叶子。

定义集合 $A={1,2,\cdots,n}$，将以下操作重复 $n-2$ 遍：

找到当前的 $A$ 中最小的不在当前数列的点 $x$，与数列开头的第一个点 $y$ 连边，在 $A$ 中删除 $x$，在数列中删除 $y$。

最后 $A$ 集合剩下的两个点连一条边。

prufer数列与树一一对应。
$n$ 个点的完全无向图的生成树个数是 $n^{n-2}$。（Caylay公式）
prufer数列中，某个点的出现次数+1=在树中该点的度数。证明显然。
对于每个点给定度数 $deg_u$，生成树个数为 $\frac{(n-2)!}{\prod(deg_u-1)!}$。

证明：由性质3，在长度为 $n-2$ 的prufer数列中，每个点 $u$ 的出现次数为 $deg_u-1$.