普呂弗序列

在圖論中，n頂點的標號樹有長n − 2的普呂弗序列。普呂弗序列在1918年首先由海因茨·普呂弗用來證明凱萊定理。

基本介紹

• 中文名：普呂弗序列
• 外文名：Prüfer sequence
• 別名：普呂弗串列
• 提出者：海因茨·普呂弗
• 適用領域：圖論

算法

一棵樹要得到普呂弗序列，方法是逐次去掉樹的頂點，直到剩下兩個頂點。考慮樹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的標號生成樹總數為n1n2其中n₂ = n − n₁。