发现自己完全不会 prufer 序列,于是来学一学.
prufer 序列是无根树的一种序列.
有标号的 $n$ 个顶点的无根树与长度为 $n-2$ ,每个元素 $\in[1,n]$ 的 prufer 序列一一对应.
构造方法
无根树 $\to$ prufer 序列
无根树的叶子定义为度数为 $1$ 的节点.
- 找到编号最小的叶子,记为 $x$ .
- 将与 $x$ 相邻的那个节点添加入 prufer 序列,然后在树中删除 $x$ .
- 重复以上操作,当整棵树只剩下两个节点时退出.
prufer 序列 $\to$ 无根树
- 取出 prufer 序列的第一个元素 $u$ ,然后将 $u$ 从 prufer 序列中删除.
- 在点集中找到没有在当前 prufer 序列中出现的最小编号的节点 $v$ ,然后将 $v$ 从点集中删除.
- 将 $u,v$ 连边.
- 重复以上操作,当点集中只剩下两个点时,将它们连边后退出.
这两种构造本质是相同的,第二种构造中每次找到的 $v$ 实际上就是第一种构造中的 $x$ ,而 $u$ 就是与 $x$ 相邻的点.
这可以说明有标号无根树与 prufer 序列的一一对应关系.
两种构造都可以用 set 来维护,时间复杂度 $O(n\log n)$ .
性质
可以从构造方法 (定义) 中找出 prufer 序列本身的一些性质.记无根树的节点数目为 $n$ .
prufer 序列的长度为 $n-2$ ,其中的每个元素都是 $1\sim n$ 中的整数.正确性显然.
$x$ 在 prufer 序列中出现的次数等于编号为 $x$ 的节点在无根树中的度数 $-1$.
证明: 与 $x$ 相邻的节点被删掉时, $x$ 会被加入 prufer 序列.若 $x$ 不是最后剩下的两个点之一,那么删除它的时候,恰好还有 $1$ 个与它相邻的节点没有被删掉,出现次数为 $ \deg-1$ .若 $x$ 是最后剩下的两个点之一,那么只有另外一个点没有被删掉,其他与 $x$ 相邻的点都被删掉了,出现次数也为 $\deg-1$ .
推论
由于 prufer 序列与无根树的一一对应关系,一些树的计数问题可以通过转化为 prufer 序列,对序列计数来求解.
Cayley 定理: $n$ 个点有标号无根树有 $n^{n-2}$ 个, 有标号有根树有 $n^{n-1}$ 个,有标号有根树森林有 $(n+1)^{n-1}$ 个.
拓展 Cayley 定理: $n$ 个有标号点形成一个 $k$ 棵树的有根树森林,若 $k$ 个根已钦定,方案数为 $k\cdot n^{n-k-1}$ ,否则再乘上 $\binom n k$ ,表示先将这 $k$ 个根选出.
证明: 记 $f(n,k)$ 表示 $n$ 个有标号点形成一个 $k$ 棵树的有根树森林, $k$ 个根已钦定时的方案数,归纳证明,奠基显然.
假定对于 $i<n$ 的 $f(i,j)$ 都已完成证明,考虑枚举编号最小的根的度数 $i$ ,将它删掉后,图会变成 $n-1$ 个点, $k+i-1$ 棵树.
$$
f(n,k)=\sum_{i=0}^{n-k} \binom{n-k}{i} \cdot f(n-1,k+i-1)
$$
代入得到 $f(n,k)=k\cdot n^{n-k-1}$ .
第 $i$ 个点的点权为 $a_i$ ,边的权值为端点点权之积,树的权值为所有边权之积,则所有树权值和为 $(\prod a_i)\cdot (\sum a_i)^{n-2}$ .
若将每个点的点权设为 $1$ ,则得到 Cayley 定理.
若将 $k$ 个根合并成一个点权为 $m$ 的点,则得到拓展 Cayley 定理.
证明:
记所求为 $ans$ .
$$
ans=\sum_{Tree} \prod_i (a_i)^{\deg(i)} \\
ans=\sum_{p} \prod_i (a_i)^{t(i)+1} \\
ans=(\prod a_i)\cdot \sum_{p} \prod_i (a_i)^{t(i)}
$$
其中 $p$ 表示任意一个 prufer 序列, $t(i)$ 表示 $i$ 在 $p$ 中出现的次数.那么后面的 $\sum$ ,相当于每个位置可以选 $a_1,a_2,\dots,a_n$ ,每个 $p$ 的贡献是选出的数之积,用乘法分配律变回去,就是 $(\sum a_i)^{n-2}$ ,于是得到 $ans=(\prod a_i)\cdot (\sum a_i)^{n-2}$ .
确定了度数,第 $i$ 个节点度数为 $\deg(i)$ 的无根树数目,由上面的性质,等价于可重排列的数目,为 $\frac{(n-2)!}{\prod (\deg(i)-1)!}$
完全图 $K_n$ 的生成树数目为 $n^{n-2}$ ,完全二分图 $K_{n,m}$ 的生成树数目为 $m^{n-1}\cdot n^{m-1}$ .
证明: 前者显然.后者的 一个证法 是根据矩阵树定理,构造出基尔霍夫矩阵,手算行列式.
用 prufer 序列也可以证明,构造 prufer 序列时,最后剩下的两个点之间有边,它们一定在二分图的两侧.
而对于其它点,每个左侧的点被删掉时,会加入一个右侧的点,每个右侧的点被删掉时,会加入一个左侧的点.
于是 prufer 序列中会有 $m-1$ 个左侧的点, $n-1$ 个右侧的点,方案数为 $m^{n-1}\cdot n^{m-1}$ .