Vexoben
Feb 20, 2019
本文介绍prufer序列的构造和相关应用,并用其得出完全图和完全二分图生成树的计算公式.
(刷新以获取数学公式)
部分内容翻译自Wikipedia.
prufer序列是带标号无根树的一种编码方式.可以证明,长度为的prufer序列和个节点的带标号无根树一一对应.
prufer序列的构造
重复以下过程:找出编号最小的度为的节点,将和它相连的点写入,删去这个叶节点,直到树上只剩两个点.
可以看出,树转prufer序列后,prufer序列长度为,每一个度数为的点在prufer序列中出现次.
将prufer序列转为树
设点集,每次取出prufer序列中最前面的元素,在中找到编号最小的没有在prufer序列中出现的元素,给连边然后分别删除,最后在中剩下两个节点,给它们连边。最终得到的就是无根树。
prufer序列相关的计数问题
给定度数序列下带标号无根树计数
设度数序列为,显然无根树数量就是.
完全图生成树计数
显然是
完全二分图生成树计数
先给出结论:设二分图X部和Y部大小分别为和,那么生成树数量为
相当于先将树黑白染色,prufer序列构造完后一定剩下一个黑点和一个白点.删去黑点时,prufer序列上写下的必定是白点;白点反之.