Prüfer 序列和 Caley 定理

· · 算法·理论

博客网址

OI Wiki讲的还挺好的。

标号无根树

其实就是把一棵无根树标一下号，让每一个节点是唯一的。

双射

一个 A 可以对应到一个唯一确定的 B，而 B 也唯一确定对应到 A，通俗不严谨来讲就是 A=B。

Prufer 序列

前提：

  1. 我们在无根树中视度数为 1 的点为叶子结点。

  2. 我们不考虑只含有 1 个结点的树。

  3. 无根树叶子结点的父节点定义为跟它相连的点（显然是唯一的）。

合法条件

只出现 1 到 n 的数、长度为 n-2 的数列都是 Prufer 序列。

构造

Prufer 序列构造依赖于一棵树。构建方法如下:

显然可以用堆模拟，也有线性构造算法(详情见 OI-WIKI)。

性质

  1. 序列中有 n-2 个数

    考虑每次加入一个点必然意味着原图边数减一，而原图有 n-1 条边且最后两个点之间的边不删，所以一共删了 n-2 条边，即加入了 n-2 个点。

  2. 剩下的两个节点中一定有一个编号是 n

    由于 n 的编号最大，所以它如果是叶子结点序列中的，那它一定是最后一个。

  3. 每个结点在序列中出现的次数是其度数减 1（没有出现的就是初始叶结点）

    一个结点如果它的度数为 z 大，那么它就和 z 个点相连，按照建树过程我们会逐渐将它的度数减小到 1 ，让它变成叶子结点从而直接删去。这个过程除了最后一条边每次度数减 1 我们都会将该点加入序列一次，也就是 z-1 次。

  4. 一个合法的 Prufer 序列和一颗树之间有双射关系 这是 Prufer 序列应用最多的性质。首先由于构造 Prufer 序列的过程是确定唯一的，所以一颗树唯一对应到一个 Prufer 序列。然后请先阅读下方重建树的内容，从中我们不难发现一个 Prufer 序列也唯一还原出生成它的那棵树，即一个 Prufer 序列也唯一对应到一颗树，所以它们满足双射关系。

重建树

由于性质 3 我们可以知道每一个点的度数，于是用两个队列来维护，一个是优先队列 P 存的是叶子编号从小到大，另一个普通队列 Q 存的是 Prufer 序列。

首先先把原图中的叶子结点加进 P ，然后从头开始遍历 Q 序列。每次选出最小编号的叶子结点，并把它跟 Q 序列队首连边，弹出两个队首。假如被弹出的 Q 队首已经连了其度数减一条边，那么就把队首加入叶子序列。最后两个点直接相连。

那么这是怎么保证还原出一颗一模一样的树呢？我们发现 Prufer 序列当前对首一定是叶子结点中编号最小的那个的根，于是我们只要还原出 Prufer 序列当前点对应的叶子集合，然后每次把队首和叶子集合中编号最小的叶子结点连边即可。

那么如何还原每一阶段的叶子集合？首先对于 Prufer 第一个点，它对应的叶子结点集合就是原树的叶子结点，由性质 3 不难得出它们。随后我们考虑一个非原树的叶子结点是什么时候加入叶子序列的，仔细重看一遍构造方法，发现当一个点变成叶子结点，即度数为 1 ，即其叶子结点被删了度数 -1 次，即被加入了度数 -1 次时，它会被加入叶子结点序列。那我们也能在这个点出现度数 -1 次时把它丢进叶子序列，这样明显可以保证还原叶子序列。

同样有线性方法重建树。

Cayley 定理

陈述

一个完全图如果大小为 n，则有 n^{n-2} 棵生成树。

证明

下面用 Prufer 序列证明。

首先我们再一次看回重建树过程，发现一个合法的 Prufer 序列（只出现 1 到 n 的数、长度为 n-2 的数列）一定是可以还原出一棵树的（它可以构造出连出 n-1 条边且没有环的图，这不就树吗），由于性质 4 我们知道这棵树和这个 Prufer 序列之间存在双射关系，所以我们只用求出对应合法 Prufer 序列个数，就可以得到生成树个数。那么接下来就是简单乘法原理了，每位有 n 种取值，长度为 n-2 数列容易证明一共有 n^{n-2} 个。

例题

可以参考一下 OI-Wiki，这里给一道巧妙运用了 Cayley 定理的题: Luogu P7718 「EZEC-10」Equalization