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序列上写下的必定是白点;白点反之.