prufer序列定义及性质

Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2

对于一棵确定的无根树,对应着唯一确定的prufer序列


树$$\to$$Prufer序列

找到度为1的点中标记最小的点,删除该点,并将与之相连的点加入序列。直到剩余两个点。

上图为[2,2,5,6][2,2,5,6]
由此可以推出,一个点在prufer序列中出现的次数为度数-1。

Prufer序列$$\to$$树

每次取出prufer序列中最前面的元素u
在点集中找到编号最小的没有在prufer序列中出现的元素v
给u,v连边然后分别删除
最后在点集中剩下两个节点,给它们连边
例如,对于prufer序列3,5,1,3
连边顺序为
2,3,
5,4,
1,5,
3,1,
3,6
(实际上与构建prufer序列时相同)
以上两种操作都可以用set维护,时间复杂度O(nlogn)

性质