Que: 对于n节点的无根树, 共有几种不同的形态 ?

Ans: n^{n-2}

引入Prüfer编码来帮助我们更好的解决问题:

对于一棵树, 进行如下操作:

  1. 寻找当前 度=1 的节点(叶), 在序列中添加其邻节点编号并且删除该点
  2. 重复上述操作, 直到图中剩两个点为止

命题

记形成的序列名为Prüfer编码

易知该序列长度为n-2, 假使证明树形态与Prüfer编码一一对应, 答案显然


每种树形态对应一个Prüfer编码

易知…

每个Prüfer编码对应一种树形态
  1. 原图的叶节点一定不会在Prüfer编码中

考虑要么这个叶节点在过程中被删除, 要么没有删除, 但是最后留下了一条边, 所以均不会在序列出现.

  1. 非叶节点一定出现在Prüfer编码中

由于最后只剩下一条边, 而非叶节点至少会有2条边与之相连, 那么就知道一定有对其的操作

构造方法:

根据前2种性质, 每次选从未在序列中出现, 且最小的数字, 操作该数与当前序列的第一位相连, 并删除序列首元素, 重复n-2​遍, 最后将未操作的两个数直接相连即可!

证毕

tricky性质:

n个节点的度依次为D_1 D_2 \cdots D_n的无根树共有\frac{(n-2)!}{\prod_{i=1}^n(D_i-1)!}个,因为此时Prüfer编码中的数字i恰好出现D_i-1次。