prufer编码

作者： 作者的头像   清风qwq ,  2023-09-12 15:47:50 ,  所有人可见 ,  阅读 174

4


$\LARGE{prufer编码}$

对于一个无根树，对它进行 $n-2$ 此操作：

  1. 找到度数最少的点中编号最小的点 $u$
  2. 找到点 $u$ 唯一连向的点 $v$ 并将其加入编码
  3. 从树上删除点 $u$

于是得到一个长度为 $n - 2$ 的序列

任何一棵树都唯一对应一个序列，且任何序列都唯一对应一颗无根树

所以 $n$ 个点的本质不同的无根树共有 $n^{n-2}$ 个

0 评论