prufer序列定义及性质

<p>Prufer数列是无根树的一种数列。在组合数学中，Prufer数列由有一个对于顶点标过号的树转化来的数列，<strong>点数为n的树转化来的Prufer数列长度为n-2</strong>。</p> <p><strong>对于一棵确定的无根树，对应着唯一确定的prufer序列</strong></p> <hr /> <h2>树$$\to$$Prufer序列</h2> <p>找到度为1的点中标记最小的点，删除该点，并将与之相连的点加入序列。直到剩余两个点。 <img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/73b6c23ed9ab01d111b2d1a96fbc02cf" alt="" /> 上图为$$[2,2,5,6]$$ <strong>由此可以推出，一个点在prufer序列中出现的次数为度数-1。</strong></p> <h2>Prufer序列$$\to$$树</h2> <p>每次取出prufer序列中最前面的元素u 在点集中找到编号最小的没有在prufer序列中出现的元素v 给u,v连边然后分别删除 最后在点集中剩下两个节点，给它们连边 例如，对于prufer序列3,5,1,3 连边顺序为 2,3， 5,4， 1,5， 3,1， 3,6 （实际上与构建prufer序列时相同） 以上两种操作都可以用set维护，时间复杂度O(nlogn)</p> <h2>性质</h2> <p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/a5e98113e5526de0db65017d60fcbef9" alt="" /> <img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/636d4fb31ba836cb134f1fd2be8d097d" alt="" /></p>