Prüfer sequence

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.

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.

Algorithm to convert a tree into a Prüfer sequence

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.

Example

[[File:Tree graph.svg|right|frame|A labeled tree with Prüfer sequence [4,4,4,5].]] 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].

Algorithm to convert a Prüfer sequence into a tree

Let [a[1], a[2], ..., a[n]] be a Prüfer sequence: The tree will have n+2 nodes, numbered from 1 to n+2 . 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 a[i] , find the first (lowest-numbered) node, j , with degree equal to 1, add the edge (j, a[i]) to the tree, and decrement the degrees of j and a[i] . 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 u , v ). Lastly, add the edge (u,v) 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

Cayley's formula

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.

Other applications

Source: Cayley's formula can be strengthened to prove the following claim: The number of spanning trees in a complete graph K_n with a degree d_i specified for each vertex i is equal to the multinomial coefficient \binom{n-2}{d_1-1,\,d_2-1,\,\dots,\,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_{n}-1)!}. The proof follows by observing that in the Prüfer sequence number i appears exactly d_i-1 times. Cayley's formula can be generalized: a labeled tree is in fact a spanning tree of the labeled complete graph. By placing restrictions on the enumerated Prüfer sequences, similar methods can give the number of spanning trees of a complete bipartite graph. If is the complete bipartite graph with vertices 1 to in one partition and vertices to in the other partition, the number of labeled spanning trees of is n_1^{n_2-1} n_2^{n_1-1} , where . Generating uniformly distributed random Prüfer sequences and converting them into the corresponding trees is a straightforward method of generating uniformly distributed random labelled trees.

References

External links

Prüfer code – from MathWorld

Text derived from https://en.wikipedia.org/w/index.php?oldid=1348527574 under CC BY-SA 4.0; modifications have been made.