prufer數列

Prufer數列是無根樹的一種數列。在組合數學中，Prufer數列由有一個對於頂點標過號的樹轉化來的數列，點數為n的樹轉化來的Prufer數列長度為n-2。它可以通過簡單的疊代方法計算出來。它由Heinz Prufer於1918年在證明cayley定理時首次提出。

辦法

將樹轉化成Prufer數列的方法

一種生成Prufer序列的方法是疊代刪點，直到原圖僅剩兩個點。對於一棵頂點已經經過編號的樹T，頂點的編號為{1,2,...,n}，在第i步時，移去所有葉子節點（度為1的頂點）中標號最小的頂點和相連的邊，並把與它相鄰的點的編號加入Prufer序列中，重複以上步驟直到原圖僅剩2個頂點。

例子

以右邊的樹為例子，首先在所有葉子節點中編號最小的點是2，和它相鄰的點的編號是3，將3加入序列並刪除編號為2的點。接下來刪除的點是4，5被加入序列，然後刪除5，1被加入序列，1被刪除，3被加入序列，此時原圖僅剩兩個點（即3和6），Prufer序列構建完成，為{3,5,1,3}

Prufer數列

將Prufer數列轉化成樹的方法

設{a1,a2,..an-2}為一棵有n個節點的樹的Prufer序列，另建一個集合G含有元素{1..n}，找出集合中最小的未在Prufer序列中出現過的數，將該點與Prufer序列中首項連一條邊，並將該點和Prufer序列首項刪除，重複操作n-2次，將集合中剩餘的兩個點之間連邊即可。

例子

仍為上面的樹，Prufer序列為{3,5,1,3}，開始時G={1,2,3,4,5,6}，未出現的編號最小的點是2，將2和3連邊，並刪去Prufer序列首項和G中的2。接下來連的邊為{4,5},{1,5},{1,3},此時集合G中僅剩3和6，在3和6之間連邊，原樹恢復。