Prufer学习小记

本文介绍prufer序列的构造和相关应用,并用其得出完全图和完全二分图生成树的计算公式.

(刷新以获取数学公式)

部分内容翻译自Wikipedia.

prufer序列是带标号无根树的一种编码方式.可以证明,长度为$n-2$的prufer序列和$n$个节点的带标号无根树一一对应.

prufer序列的构造

重复以下过程:找出编号最小的度为$1$的节点,将和它相连的点写入,删去这个叶节点,直到树上只剩两个点.

可以看出,树转prufer序列后,prufer序列长度为$n-2$,每一个度数为$d$的点在prufer序列中出现$d-1$次.

将prufer序列转为树

设点集$V={1,2,3,...,n}$，每次取出prufer序列中最前面的元素$u$，在$V$中找到编号最小的没有在prufer序列中出现的元素$v$，给$u，v$连边然后分别删除，最后在$V$中剩下两个节点，给它们连边。最终得到的就是无根树。

prufer序列相关的计数问题

给定度数序列下带标号无根树计数

设度数序列为$D=(d_1,d_2,...d_n)$,显然无根树数量就是$\frac{(n-2)!}{(d_1-1)!(d_2-1)!...(d_n-1)!}$.

完全图生成树计数

显然是$n^{n-2}$

完全二分图生成树计数

先给出结论:设二分图X部和Y部大小分别为$n_1$和$n_2$,那么生成树数量为$n_1^{n_2-1}n_2^{n_1-1}$

相当于先将树黑白染色,prufer序列构造完后一定剩下一个黑点和一个白点.删去黑点时,prufer序列上写下的必定是白点;白点反之.