Prüfer sequence

Template:Short description 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 Template:Mvar vertices has length Template:Math, 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 Template:Mvar with vertices Template:Math. At step Template:Mvar, remove the leaf with the smallest label and set the Template:Mvar-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 Template:Math.

Both coding and decoding can be reduced to integer radix sorting and parallelized.

Example

File:Tree graph.svg

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(Template:Mvar)
 1 Template:Mvar ← length[[[:Template:Mvar]]]
 2 Template:Mvar ← a graph with Template:Mvar + 2 isolated nodes, numbered 1 to Template:Mvar + 2
 3 degree ← an array of integers
 4 for each node Template:Mvar in Template:Mvar do
 5     degree[[[:Template:Mvar]]] ← 1
 6 for each value Template:Mvar in Template:Mvar do
 7     degree[[[:Template:Mvar]]] ← degree[[[:Template:Mvar]]] + 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 Template:Mvar in Template:Mvar do
 9     for each node Template:Mvar in Template:Mvar do
10         if degree[[[:Template:Mvar]]] = 1 then
11             Insert edge[[[:Template:Mvar]], Template:Mvar] into Template:Mvar
12             degree[[[:Template:Mvar]]] ← degree[[[:Template:Mvar]]] - 1
13             degree[[[:Template:Mvar]]] ← degree[[[:Template:Mvar]]] - 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 Template:Mvar ← Template:Mvar ← 0
16 for each node Template:Mvar in Template:Mvar
17     if degree[[[:Template:Mvar]]] = 1 then
18         if Template:Mvar = 0 then
19             Template:Mvar ← Template:Mvar
20         else
21             Template:Mvar ← Template:Mvar
22             break
23 Insert edge[[[:Template:Mvar]], Template:Mvar] into Template:Mvar
24 degree[[[:Template:Mvar]]] ← degree[[[:Template:Mvar]]] - 1
25 degree[[[:Template:Mvar]]] ← degree[[[:Template:Mvar]]] - 1
26 return Template:Mvar

Cayley's formula

The Prüfer sequence of a labeled tree on Template:Mvar vertices is a unique sequence of length Template:Math on the labels 1 to Template:Mvar. For a given sequence Template:Mvar of length Template:Math on the labels 1 to Template:Mvar, there is a unique labeled tree whose Prüfer sequence is Template:Mvar.

The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on Template:Mvar vertices and the set of sequences of length Template:Math on the labels 1 to Template:Mvar. The latter set has size Template:Math, so the existence of this bijection proves Cayley's formula, i.e. that there are Template:Math labeled trees on Template:Mvar 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

$(\genfrac{}{}{0ex}{}{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 Template:Mvar is the complete bipartite graph with vertices 1 to Template:Math in one partition and vertices Template:Math to Template:Mvar in the other partition, the number of labeled spanning trees of Template:Mvar is $n_1^{n_2-1}{n}_2^{n_1-1}$, where Template:Math.
• 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.

External links

• Prüfer code – from MathWorld