Prufer序列和Cayley公式
首先定义无根树中度数为1的节点是叶子节点。
找到编号最小的叶子并删除，序列中添加与之相连的节点编号，重复执行直到只剩下2个节点。
这个序列为这棵树的 Prufer 序列。
一棵有 \(n\) 个节点的无根树的 Prufer 序列的长度为 n-2。
显然，一棵无根树可以一一对应一个 Prufer 序列。
而且长度为 \(n-2\) 的元素可重复序列有 \(n^{n-2}\) 种可能。
那么有 \(n\) 个节点的无向图就有 \(n^{n-2}\) 种不同的生成树，
或者说一颗有 \(n\) 个节点的无根树有 \(n^{n-2}\) 种不同的形态。
这两个描述是等价的，这个结论叫做 Cayley 公式。
那如果是有根树呢？
因为有根树的每个节点都可以作为根，
所以一颗有 \(n\) 个节点的有根树有 \(n^{n-1}\) 种不同形态。