OI Wiki讲的还挺好的。
标号无根树
其实就是把一棵无根树标一下号，让每一个节点是唯一的。
双射
通俗来讲就是一个 \(A\) 可以对应到一个唯一确定的 \(B\)，反之也是如此。
Prufer序列
构造
Prufer 序列的构建方法如下:
-
找到一棵树的最小叶子结点,删除它,并往序列尾端加入它的父节点编号
-
如果它的父节点变成叶子结点，将它丢到叶子结点的序列中
-
重复直到只剩两个点
性质
-
序列中有 \(n-2\) 个数
这不易证吗。
-
剩下的两个节点中一定有一个编号是 \(n\)，另一个是根节点
由于 \(n\) 的编号最大，所以它如果是叶子结点序列中的，那它一定是最后一个，如果根节点，那更不必说了,它的一定会有一个叶子结点(即是 \(n\) )。
-
每个结点在序列中出现的次数是其度数减 \(1\) 。（没有出现的就是叶结点）
一个结点会被它的每一个叶子结点入序列一次，非根结点由于还有一条到父亲，根节点