prufer序列筆記

prufer序列

度娘的定義

Prufer數列是無根樹的一種數列。在組合數學中，Prufer數列由有一個對于頂點标過号的樹轉化來的數列，點數為n的樹轉化來的Prufer數列長度為n-2。

對于一棵确定的無根樹，對應着唯一确定的prufer序列

構造方法

無根樹轉化為prufer序列

1. 找到編号最小的度數為\(1\)的點
2. 删除該節點并在序列中添加與該節點相連的節點的編号
3. 重複\(1,2\)操作，直到整棵樹隻剩下兩個節點

如下圖的prufer序列為\(3,5,1,3\)

prufer序列轉化為無根樹

1. 每次取出prufer序列中最前面的元素\(u\)
2. 在點集中找到編号最小的沒有在prufer序列中出現的元素\(v\)
3. 給\(u,v\)連邊然後分别删除
4. 最後在點集中剩下兩個節點，給它們連邊

例如，對于prufer序列\(3,5,1,3\)

連邊順序為

\(2,3\)，

\(5,4\)，

\(1,5\)，

\(3,1\)，

\(3,6\)

（實際上與建構prufer序列時相同）

以上兩種操作都可以用set維護，時間複雜度\(O(nlogn)\)

性質

1. prufer序列中某個編号出現的次數就等于這個編号的節點在無根樹中的度數-1
2. 一棵n個節點的無根樹唯一地對應了一個長度為n-2的數列，數列中的每個數都在1到n的範圍内。
3. \(n\)個點的無向完全圖的生成樹的計數：\(n^{(n-2)}\)，即\(n\)個點的有标号無根樹的計數
4. n個節點的度依次為\(d_1,d_2,…,d_n\)的無根樹共有\(\frac{(n-2)!}{ \prod_{i=1}^n(d_i-1)!}\)個，因為此時Prufer編碼中的數字\(i\)恰好出現\(d_i-1\)次，\((n−2)!\)是總排列數
5. n個點的 有标号有根樹的計數：\(n^{(n-2)}*n = n^{(n-1)}\)

暫且寫這些吧，先做做題，然後繼續整理

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。