prefur序列及Cayley公式

一.写在前面

p.s 学习自https://www.cnblogs.com/dirge/p/5503289.html

二.prefur序列

1.由无根树生成prefur序列

首先定义无根树中度数为1的节点是叶子节点。
找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下2个节点。

2.由prefur序列生成无根树

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

3.Cayley公式

给出n个点，这n个点能构成\(n^{n-2}\)颗无根树

三.性质

1.prefur序列与无根树一一对应

2.度数为\(d_i\)的点在prefur中出现\(d_i\)-1次

3.对于给定度数\(d_1\)~\(d_n\)的无根树共有\(\dfrac{(n-2)!}{\prod_{i=1}^{n}{(d_i-1)}}\)种