Prufer编码

Published: by Creative Commons Licence

  • Tags:

Prufer编码

prufer编码与树一一对应,可以用于计数树的种类。

先说明如何将一颗树转换为prufer编码。如果树中还剩余多于两个顶点,那么就选择度为1的编号最小的顶点,并将其从树中移除,同时将树中原本唯一与它相连的顶点加入到编码序列尾部。重复该操作直到跳出条件满足。

下面说明将prufer编码转换为树的步骤。维护一个顶点集合X,初始的时候其中包含了所有不出现在prufer编码序列中的顶点。首先从X中移除编号最小的顶点v,并从prufer编码序列中移除最前面的顶点u,在u、v之间连接一条边,如果u不再出现在prufer编码序列中,就将u加入到X中。重复上面的操作直到prufer序列为空。

这里说明一下树转prufer和prufer转树是互逆操作。初始时X集合中仅包含叶子结点,而叶子结点中编号最小的那个结点v一定是在树转prufer时第一个被选择的顶点,之后该顶点的相邻顶点u作为prufer序列的第一个元素。因此我们在prufer转树的第一步就将这两个结点连边。之后的prufer序列对应删除了v后的新树,这里可以用归纳原理证明还原的正确性。

由于树和prufer编码一一对应,我们可以容易发现n个顶点可以组成的树的数目等于$n^{n-2}$。

现在说明prufer编码的性质。

  1. 如果一个顶点在原树中的度数为d,那么在prufer编码中包含d-1个该顶点。

提供两道用到prufer编码技术的题目:LUOGU2624Codeforces1109D