Purfer序列

我们经常干的一件事是把数变为关于图的问题来解决，那么久了未免不会有这个疑问：能不能把图变成数来解决问题？

所以有了这个purfer数列。

介绍一下这个数列有什么用（或者说有什么性质）：

能够将一棵无根树转化成一个数列，且按这种编码数列具有唯一性

2.给定一purfer数列，可以还原出原来的无根树，且有且仅有一种方法。

那么这个数列是怎么形成的呢？下面来大概叙述一下整个过程：

（1）生成数列：

选取此时树上编号最小的叶子节点，删除此节点且将此节点所连接的节点加入数列末端

不断的重复上述操作，直到只剩两个节点时停止该操作。

（所以一个purfer序列的长度应为n-2）

（2）还原无根树：

设集合A = {1，2，3，...... ，n-1， n}

设purfer数列 a1， a2， ...... ， an

顺次选出purfer数列首位元素，然后在集合A中选出另一元素与它相连边

选出元素需满足一下特点：

① 该元素此时不能在purfer序列中

② 该元素此时应在集合A中

③ 满足以上两条件的最小元素

不断进行以上操作，知道purfer数列为空，此时A集合必然存在两个元素，最后将这两个元素连接起来，则此无根树还原完毕。

具体样例如下：

purfer编码为 1 2 2

那么来思考几个问题：

（1）为什么此方法能够还原？

我认为可以这样想，首先（用上面的例子来说），你是先删除了一个点3，然后再把这个点所连的一个点1加入purfer的。那么显然你这个点3一定不在是、此时的purfer中，对吧？同样的道理，无论什么时候，你purfer的首位所连接的数一定不在后面的队列中（因为你要先删除他，然后再把这个数所连接的数加入purfer），而由于我们每次都找的是编号最小的数，所以我们把有可能的数中找出最小数就好了，就能够唯一确定了。而由于每个数最多只能被删一次，所以A集合中的数用完之后就要删去，他也只能被用一次。所以purfer中一共有n-2个数，就有n-2次操作，就连了n-2条边。而你最后仅剩下的两个数有且仅有一种选择就是连最后一条边，所以综上就是n个点，连接n-1条边，这必然就是一棵树了。

（2）这样还原的一个特殊性质：（虽然说是无根树，我们假设它初具树形233，就是假装有儿子和父亲节点）

有观察可以得到，如果说一个点本来就是叶节点，那么他就悲剧了，他一来就直接被删了，根本就没有机会进入purfer；而如果像图中的节点1就要稍稍幸运一些，他要在节点3被删了以后才被删，而节点3被删时他就可以进入一次purfer数列；那么一个点什么时候会被删呢？当然是他是叶子节点的时候，也就是度为1的时候；那么怎么才能成为叶子节点？很简单，你的周围所连接的其他儿子点都被解决之后你就成为了叶子节点；换句话说，假设你周围有n个儿子节点，那么你就有n次进入purfer的机会，再进一步就可以得到一个很重要的结论：一个点的度数 = 它在purfer中出现的次数 + 1（它和父节点的连边）

巴特西

Purfer序列

最新文章

热门文章