prufer 序列学习笔记
知识点
前言
prufer 序列是为了证明 Cayley 公式而被发明出来的，即一个 \(n\) 个点的完全图共有 \(n^{n-2}\) 个不同的树。
prufer 序列可以将一个 \(n\) 个点的树唯一映射到一个长度为 \(n-2\) 的序列上，即两棵树不同当且仅当它们的 prufer 序列不同。
prufer 序列的构造
每次找到编号最小的一个叶子节点，将与其相连的节点加入序列，并将其在树上删除，直到树上只有两个节点。
prufer 序列具有以下两个性质：
- 树中最后剩下的两个点中，一定存在一个节点是编号最大的点 \(n\)
- 每个节点在序列中出现的次数为这个点的度数 \(-1\)。