树的Prufer 编码和最小生成树计数

2017年08月25日 11点热度 0人点赞 0条评论

1. 一棵标号树的Pufer编码规则如下:找到标号最小的叶子节点,输出与它相邻的节点到prufer 序列, 将该叶子节点删去,反复操作,直至剩余2个节点。

 

2. 由Pufer编码生成树:任何一个prufer 序列可以唯一对应到一棵有标号的树,首先标记所有节点为未删除 依次扫描prufer 序列中的数,比如当前扫描到第k个数u,说明有一个叶子节点连到u,并在当前操作中被删除,找一个标号最小的未被标记为删除的且在prufer 序列第k个位置后未出现过的节点v,在u,v间连边并将v删除,反复操作,最后剩两个节点未被标记为删除,在它们之间连边,这样得到的一个图含有n-1条边则是一棵树

3. 一棵树N个结点,其Profer序列有N-2个位置,因此可以在这N-2个位置里面任何的填充1~N之间的数形成一个prufer序列,且一个prufer序列唯一的对应一颗生成树,于是完全图的最小生成树的数目为N^(N-2)

 

推荐做题:pku2567,pku2568

未经允许不得转载!树的Prufer 编码和最小生成树计数

update

纸上得来终觉浅, 绝知此事须躬行。