20220106-Prufer编码

发表于 2022-01-06 更新于 2022-01-08 阅读次数：本文字数： 406 阅读时长 ≈ 1 分钟

树编码为Prufer序列：Prufer序列初始为空。每次从树上选出一个编号最小的叶子节点，然后将与该叶子节点相邻的那个节点的编号写入prufer序列的末尾，之后从树上删掉这个叶子节点。循环这个步骤n-2次，最后得到一个长度为n-2的prufer序列（此时树中只有一条边，我们就不管它了）。具体步骤演示见参考
由Prufer序列得到树：首先，将每个节点的度数设为1加上该节点在Prufer序列中出现的次数。然后以下循环执行n-2次。第i次循环，选择此时度数为1的编号最小的节点u，将其与此时Prufer序列的第i个元素v连边，然后将u和v的度数都减去1。这n-2次执行完之后，仅剩下两个节点他们的度数都是1，将这两个点连边，这样就得到一个有n-1条边的树。具体步骤演示见参考
Cayley公式：n个节点带标号的无根树有$n^{n-2}$个。