普呂弗序列

維基百科,自由的百科全書

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

算法[編輯]

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

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

這棵標號樹有普呂弗序列{4,4,4,5}。

例子[編輯]

把上述算法用在右圖標號樹。第一步,頂點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的序列共有nn−2個,這樣就證明了凱萊公式,就是n頂點的標號樹共有nn−2棵。

這個結果可以推廣:一棵標號樹實際上是標號完全圖的一棵生成樹。對普呂弗序列加以限制。類似的方法可以得到標號完全二部圖的生成樹總數。若G是完全二部圖,一部分的頂點標號1到n1,另一部分的頂點標號n1 + 1到nG的標號生成樹總數為,其中n2 = n − n1

參考[編輯]

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