Prüfer 序列学习笔记
如何优美地数树 ~ Prüfer 序列学习笔记
Prüfer 序列
首先定义无向树的 Prüfer 序列:
对于一颗无向树,考虑按照下列步骤建立 Prüfer 序列:
- 删去当前编号最小的叶子节点,并在序列中加入其父亲节点;
- 重复 \(n-2\) 次直到剩下两个节点。
最终得到的序列就是该无向树的 Prüfer 序列。
用堆暴力构造是 \(O(n\log n)\) 的,有一个线性构造办法:
记录指针 \(p\) 和每个点的度数 \(\deg_i\),按照以下步骤建立序列:
- 若 \(p\) 为叶子节点,删除节点 \(p\)(不改变指针 \(p\) 的位置);
- 判断是否产生新的叶子节点。若产生,则判断新叶子节点编号 \(q\) 与 \(p\) 的大小关系。若 \(q<p\),则立即删除 \(q\),重复步骤 \(2\);否则不进行操作;
- 自增 \(p\) 直到变为步骤 \(1\)。
正确性是显然的,时间复杂度 \(O(n)\)。
根据 Prüfer 序列可以唯一地重建树。方法与建立类似。
Prüfer 序列实际上与无向树构成了双射关系,用处就是数树。
性质:结点 \(i\) 在序列中出现的次数是 \(\deg_i-1\)。
Cayley 公式
Cayley 公式:\(n\) 个标号点形成的树的数量为 \(n^{n-2}\)。
等价于:完全图 \(K_n\) 的生成树个数为 \(n^{n-2}\)。
用 Prüfer 序列可以方便地证明 Cayley 公式.
证明:任意一个长度为 \(n-2\) 的,值域为 \([1,n]\) 的 Prüfer 序列都是原图的一棵生成树。证毕。
广义 Cayley 公式
广义 Cayley 公式:\(n\) 个标号点形成一个有 \(k\) 颗树的森林,使给定的 \(k\) 个点中任两点不属于同一棵树的方案数为 \(k\cdot n^{n-k-1}\)。
证明:不妨钦定给定的 \(k\) 个点分别为 \(k\) 颗树的根。我们建立一个虚根 \(I\),钦定其编号为 \(n+1\),并分别钦定 \(k\) 个点编号为 \(n-k+1\sim n\)。
由于 Prüfer 序列每次删叶子节点,因此这 \(k\) 个点一定是最后被删除的,并且加入序列的数一定是 \(n+1\)。也就是说,Prüfer 序列最后 \(k-1\) 个点一定是 \(n+1\)。
编号为 \(n-k-2\) 的节点,其父亲一定只能是这 \(k\) 个点。剩余的 \(n-k-1\) 个点,其父亲可以是 \([1,n]\) 中任意节点。
因此最终的方案数就是 \(k\cdot n^{n-k-1}\)。
- 标题: Prüfer 序列学习笔记
- 作者: 夏佑 | XiaU
- 创建于 : 2023-10-03 00:00:00
- 更新于 : 2023-10-03 10:33:50
- 链接: https://summace.cc/Prufer/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。