prufer序列

\(prufer\)序列

大部分树上计数问题，都可以用它的性质来解决。

1：从无根树到\(prufer\)序列：

重复进行以下操作直到树中剩两个节点。

1：找到度数为1的编号最小的节点。

2：将其父节点加入队列，将这点删去。

则该树的\(prufer\)序列为\(\left\{ 1,2,1,3,3,1\right\}\)

2：从\(prufer\)序列到无根树：

1：取出\(prufer\)序列最前面的元素\(x\)。

2：取出在点集中的、且当前不在\(prufer\)序列中的最小元素\(y\)。

3：在\(x,y\)之间连接一条边。

4：我们在点集中剩下的两个点中连一条边。

3：重要性质：

1：\(prufer\)序列与无根树一一对应。

2：度数为\(d_i\)的节点会在\(prufer\)序列中出现\(d_i-1\)次。

3：一个\(n\)个节点的完全图的生成树个数为\(n^{n-2}\)。

4：对给定度数\(d_1,d_2,\cdots,d_n\)的无根树共有\(\dfrac{\left( n-2\right) !}{\Pi _{i,=1}^{n}\left( d_{i}-1\right) }\)种。