Prüfer 序列学习笔记

· · 算法·理论

0. 前言

Prüfer 序列，在 NOI 大纲中属于 9 级，是一个比较冷门（？）的算法。Prüfer 序列的实现与理解是十分简单与易懂的，这篇文章会将笔者学习 Prüfer 序列 的经历简要概述，非常适合初学者进行阅读。

1.Prüfer 序列概念引进

1.1 举例

我们引进一颗较为简单的树，如下图：

我们进行下列操作：

  1. 找到当前树中叶子节点中编号最小的，记为 u_i。
  2. 选定与 u_i 相连接的节点，记为 v_i。
  3. 将 v_i 加入一个用于记录的序列，然后删除节点 u_i 和 u_i - v_i 的连边，重复上述操作直到原图仅剩两个节点。

例如上图中给定的例子最终得到的序列为 {3,1,5,5,1}。

我们可以发现，由于一棵树每一次被选定的节点是固定的，所以对于每一棵不同的树都对应着一个上述中的序列，我们称这个序列为Prüfer 序列。

可证明一个 Prüfer 序列是对应唯一一棵树且可以与其相互转化的。

1.2 证明

1.2.1 树对应的序列的唯一性

这个很好证明，因为对于一棵树经历过若干次操作后的状态，接下来操作的节点是可确定的。

1.2.2 序列转换成树

我们还是拿上图举例。

已知有一颗有标号的顶点的树，节点数量为 7，其的 Prüfer 序列为 {3,1,5,5,1}，需求出这棵树。

注意到在一棵树的 Prüfer 序列中未出现的节点一定为这棵树的叶子结点。

我们将所有叶子结点首先加入一个最小堆，容易发现第一次操作选中的是 Prüfer 序列的第一项与编号最小的一个叶子节点的连边，于是我们将此连边选中。

例如在序列 {3,1,5,5,1} 中，我们会将连边 {2-3} 选中。

由于 2 号节点已有连边，所以并不是叶子结点，将 2 号节点从存储叶子结点的堆中弹出。发现 3 号节点不再在 Prüfer 序列中存在连边，所以删去连边 {2-3} 后节点 3 成为了叶子结点。将节点 3 加入维护叶子结点的堆并重新维护最小值，原 Prüfer 序列也变为 1,5,5,1，发现可以递归求解。

容易发现递归边界为 Prüfer 序列中仅存在一个节点 1，而此时存储叶子结点的堆中仅有一个节点 7。所以此时我们将连边 1-7 加入，并结束递归，我们就完成了对树的转换。

我们可以把上面归成下面几个步骤：

  1. 将原 Prüfer 序列中未存在的点加入维护叶子结点编号最小值的堆，并记录所有节点在原 Prüfer 序列中出现的次数；
  2. 选中当前 Prüfer 序列第一个节点，将该节点与当前最小的叶子结点进行连边；
  3. 将选中的最小叶子结点从堆中删除，当前第一个节点减去 1，如果该节点次数减至 0，将其加入叶子结点的堆。
  4. 删去当前 Prüfer 序列第一个节点，并重新维护叶子结点最小值。回到第二步继续执行操作直到无法操作。

至此，我们完成了由 Prüfer 序列向树的转换，接下来要证明 Prüfer 序列对应的树的唯一性。

1.2.3 序列对应树的唯一性

发现我们在 1.2.2 中将序列转换成树的操作每一步都是唯一的，所以一个 Prüfer 序列对应的树的每一条边都是唯一的，自然这棵树是唯一的。

由这个结论我们可以很轻松地证明 Cayley 定理。

Cayley 定理 : n 个有标号的顶点的树的数目为 n^{n-2}。

我们可以发现，n 个有标号的顶点的树的数目即为 n 个有标号的顶点的树可以组成的 Prüfer 序列个数。

可以发现 Prüfer 序列的 n-2 个节点都可以从 n 个节点中选择一个且互不干扰，总选择方案数为 n^{n-2}，原定理得证。

2. Prüfer 序列相关例题

Prüfer 序列模板题：P6086 【模板】Prufer 序列

Cayley 定理模板题：UVA10843 Anne's game

3. 后言

这里本应该有一些长篇大论的东西，但笔者觉得没必要写就咕了。

欢迎补充和指出问题awa