普呂弗序列

在圖論中，標號樹的普呂弗序列（英語：Prüfer sequence）是由樹唯一地產生的序列。n頂點的標號樹有長n − 2的普呂弗序列，可以從一個簡單的迭代算法得到。普呂弗序列在1918年首先由海因茨·普呂弗用來證明凱萊公式。

算法

一棵樹要得到普呂弗序列，方法是逐次去掉樹的頂點，直到剩下兩個頂點。考慮樹T，其頂點為{1, 2, ..., n}。在第i步，去掉標號最小的葉，並把普呂弗序列的第i項設為這葉的鄰頂點的標號。

一棵樹的序列明顯是唯一的，而且長為n − 2。

例子

把上述算法用在右圖標號樹。第一步，頂點1是最小標號的葉，因此首先去掉，普呂弗序列首項是"4"，接着去掉頂點2和3，"4"兩次加進序列。頂點4現在是葉，去掉後剩下2個頂點，所以把"5"加進序列後結束。樹的序列是{4,4,4,5}。

復原算法

從一個普呂弗序列，可以求得一棵樹有這一普呂弗序列。

設這普呂弗序列長n − 2。首先寫出數1至n。第一步，找出1至n中沒有在序列中出現的最小數。把標號為這數的頂點和標號為序列首項的頂點連起來，並把這數從1至n中刪去，序列的首項也刪去。接着每一步以1至n中剩下的數和餘下序列重複以上步驟。最後當序列用完，把1至n中最後剩下的兩數的頂點連起來。

應用

一棵樹的序列明顯地是唯一的，但比較不明顯的是，一個長為n−2且每項都在1至n之間的序列S，有唯一的標號樹以S為普呂弗序列。這個結果可以對n用數學歸納法證明。

從這結果立刻可知，普呂弗序列給出長n−2的序列和有n頂點的標號樹之間的一一映射。長n−2的序列共有nⁿ⁻²個，這樣就證明了凱萊公式，就是n頂點的標號樹共有nⁿ⁻²棵。

這個結果可以推廣：一棵標號樹實際上是標號完全圖的一棵生成樹。對普呂弗序列加以限制。類似的方法可以得到標號完全二部圖的生成樹總數。若G是完全二部圖，一部分的頂點標號1到n₁，另一部分的頂點標號n₁ + 1到n。G的標號生成樹總數為 $n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}$ ，其中n₂ = n − n₁。

參考

Prüfer, H. Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 1918, 27: 742–744.