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

Ans: n^{n-2}

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

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

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

命题

记形成的序列名为Prufer编码.

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


Proof

一、每种树形态对应一个Prufer编码

易知…

二、每个Prufer编码对应一种树形态

  1. 原图的度为1的节点一定不会在Prufer编码中

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

  1. 度大于1的节点一定出现在Prufer编码中

由于最后只剩下一条边, 而非叶节点至少会有2条边与之相连。
故一定有对其加入序列的操作

  • 构造方法: 根据前2种性质,

    每次选从未在序列中出现, 且编号最小的节点

    操作该节点与当前序列的第一位相连, 并删除序列首元素

    重复n-2遍, 最后将序列剩下的2个节点直接相连即可

Trick

  • n个节点的度依次为D_1 D_2 \cdots D_n的无根树共有\frac{(n-2)!}{\prod_{i=1}^n(D_i-1)!}

    因为此时Prufer编码中的数字i恰好出现D_i-1次。

upd(2019.9)

了(ji)解(zhu)以下结论:

  • 能够成二分图的带标号无根树方案数为n^{m-1}m^{n-1}

n,m为二分图两侧点集大小。

  • n个带标号节点当前已经形成m个连通块, 且第i个连通块大小为a_i
    添加边, 使得它变成一棵树的方案数为n^{m-2}\prod_i a_i.

这里给出2的证明.

Proof

m个连通块缩点, 它所构成的prufer方案数为m^{m-2}.

但, 这里的点是连通块, 故一条(u, v)的边两端节点的选择有a_u\cdot a_v种.

进一步的:

\prod_{(u, v)\in E} a_u\cdot a_v=\prod_{i=1}^m a_i^{c_i + 1}

其中, c_i表示i号连通块在prufer序列中的出现次数.

显然, \sum_{i=1} ^ m c_i = m – 2

+1提取出来, 考虑n个节点连边的总方案数就是:

\begin{aligned} &\sum_{\text{P is a prufer array }} \sum_{i=1}^m a_i^{c_i}\\ &=(a_1+a_2+\dots+a_m)^{m-2}\\ &=n^{m-2}\\ \end{aligned}