Prufer序列和Cayley定理

OI Wiki讲的还挺好的。

标号无根树

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

双射

通俗来讲就是一个 \(A\) 可以对应到一个唯一确定的 \(B\)，反之也是如此。

Prufer序列

构造

Prufer 序列的构建方法如下:

• 找到一棵树的最小叶子结点,删除它,并往序列尾端加入它的父节点编号

• 如果它的父节点变成叶子结点，将它丢到叶子结点的序列中

• 重复直到只剩两个点

性质

1. 序列中有 \(n-2\) 个数

   这不易证吗。

2. 剩下的两个节点中一定有一个编号是 \(n\)，另一个是根节点

   由于 \(n\) 的编号最大，所以它如果是叶子结点序列中的，那它一定是最后一个，如果根节点，那更不必说了,它的一定会有一个叶子结点(即是 \(n\) )。

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

   一个结点会被它的每一个叶子结点入序列一次，非根结点由于还有一条到父亲，根节点