In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on vertices has length , and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.
One can generate a labeled tree's Prüfer sequence by iteratively removing vertices from the tree until only two vertices remain. Specifically, consider a labeled tree with vertices . At step , remove the leaf with the smallest label and set the -th element of the Prüfer sequence to be the label of this leaf's neighbour.
The Prüfer sequence of a labeled tree is unique and has length .
Both coding and decoding can be reduced to integer radix sorting and parallelized.
Consider the above algorithm run on the tree shown to the right. Initially, vertex 1 is the leaf with the smallest label, so it is removed first and 4 is put in the Prüfer sequence. Vertices 2 and 3 are removed next, so 4 is added twice more. Vertex 4 is now a leaf and has the smallest label, so it is removed and we append 5 to the sequence. We are left with only two vertices, so we stop. The tree's sequence is [4,4,4,5].
Let <code>[a[1], a[2], ..., a[n]]</code> be a Prüfer sequence:
The tree will have <code>n+2</code> nodes, numbered from <code>1</code> to <code>n+2</code>. For each node set its degree to the number of times it appears in the sequence plus 1. For instance, in pseudo-code:
Convert-Prüfer-to-Tree() 1 â length[] 2 â a graph with + 2 isolated nodes, numbered 1 to + 2 3 degree â an array of integers 4 for each node in do 5 degree[] â 1 6 for each value in do 7 degree[] â degree[] + 1
Next, for each number in the sequence <code>a[i]</code>, find the first (lowest-numbered) node, <code>j</code>, with degree equal to 1, add the edge <code>(j, a[i])</code> to the tree, and decrement the degrees of <code>j</code> and <code>a[i]</code>. In pseudo-code:
8 for each value in do 9 for each node in do 10 if degree[] = 1 then 11 Insert edge[, ] into 12 degree[] â degree[] - 1 13 degree[] â degree[] - 1 14 break
At the end of this loop two nodes with degree 1 will remain (call them <code>u</code>, <code>v</code>). Lastly, add the edge <code>(u,v)</code> to the tree.
15 â â 0 16 for each node in 17 if degree[] = 1 then 18 if = 0 then 19 â 20 else 21 â 22 break 23 Insert edge[, ] into 24 degree[] â degree[] - 1 25 degree[] â degree[] - 1 26 return
The Prüfer sequence of a labeled tree on vertices is a unique sequence of length on the labels 1 to . For a given sequence of length on the labels 1 to , there is a unique labeled tree whose Prüfer sequence is .
The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on vertices and the set of sequences of length on the labels 1 to . The latter set has size , so the existence of this bijection proves Cayley's formula, i.e. that there are labeled trees on vertices.
Source: