Chlience

【算法】Prufer 编码
$Prufer$ 编码,是对于有标号无根树的一种唯一表示方式如何求 $Prufer$ 编码给定一棵带标号无根树,找...
扫描右侧二维码阅读全文
26
2019/02

【算法】Prufer 编码

$Prufer$ 编码,是对于有标号无根树的一种唯一表示方式

如何求 $Prufer$ 编码

给定一棵带标号无根树,找出当前编号最小的叶子节点(度为 $1$ 的节点),并写下其相邻接点的编号,最后删掉该叶子节点

反复执行上述操作知道只剩下两个节点为止

$Prufer$ 编码与无根树的对应关系

显然,一个节点数 $n$ 的无根树对应着一个长度为 $n-2$ 的$Prufer$ 编码数列

并且可以发现, $Prufer$ 编码中的点不可能是原图中的叶子
假设数列中出现了某个点是原图中的叶子,当且仅当其相邻点被删除,也就是说整棵树只剩下了一个节点,而算法到最后至少有两个节点,矛盾

同样, $Prufer$ 编码中没有出现的点是否恰好就是原图中的叶子呢?

答案是肯定的
由于原图中的任意一个非叶子节点,必然有至少两个相邻节点,而算法最后剩下的两个点都仅有一个相邻节点,也就是说所有的非叶子节点至少被其一个相邻节点统计

或者换句话说,一个点在 $Prufer$ 中出现的次数就是其度数 $-1$

那么我们可以通过这样的方式来还原一棵树:

一开始有可能是最小叶子节点的待选序列中只有 $Prufer$ 编码中没有出现过的点,取较小者,连接 $Prufer$ 编码的第一位

显然,该点不可能再与任意点连接,直接将其删除

接下来待选序列中的点便是前 $n-3$ 位中没有出现过的点(除了已经使用过的最小点

重复以上操作,直到当前序列为空

那么这一个 $Prufer$ 编码就对应这样一棵无根树

也可以说, $Prufer$ 编码序列和无根树之间满足双射关系

推广

度数依次为 $D_1,D_2,\cdots,D_n$ 的 $n$ 个节点能组成的无根树一共有 $\frac{(n-2)!}{(D_1-1)!(D_2-1)!\cdots(D_n-1)!}$
也就是对应的 $Prufer$ 编码的个数

Last modification:February 26th, 2019 at 04:39 pm

Leave a Comment