本文共 695 字，大约阅读时间需要 2 分钟。

最近做到一些题，用到了Prufer序列，挺有用的，在这里学习一下。

描述

Prufer数列是无根树的一种数列，通过一个Prufer序列可以唯一表示一棵顶点带标号的无根树，点数为n的树转化来的Prufer数列长度为n-2，它有很多的性质

求法

一种生成Prufer序列的方法是迭代删点，直到原图仅剩两个点。对于一棵顶点已经经过编号的树T，顶点的编号为{1,2,…,n}，在第i步时，移去所有叶子节点（度为1的顶点）中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列中，重复以上步骤直到原图仅剩2个顶点

转回

现在有一个prufer序列，如何推回原本的无根树呢？

作用

比如，现在有一棵$n$个节点的树，给定每个节点的度数，求树可能形态数，答案为：$$\frac{(n-2)!}{{\prod }_{i=1}^n(d_i-1)!}$$

待upd

转载地址：https://blog.csdn.net/zhouyuheng2003/article/details/80789407 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！