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 n vertices has length n − 2, 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 T with vertices {1, 2, ..., n}. At step i, remove the leaf with the smallest label and set the i-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 n − 2.

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

Example

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:

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:

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.

Cayley's formula

The Prüfer sequence of a labeled tree on n vertices is a unique sequence of length n − 2 on the labels 1 to n. For a given sequence S of length n − 2 on the labels 1 to n, there is a unique labeled tree whose Prüfer sequence is S.

The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on n vertices and the set of sequences of length n − 2 on the labels 1 to n. The latter set has size nn−2, so the existence of this bijection proves Cayley's formula, i.e. that there are nn−2 labeled trees on n 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 {\displaystyle K_{n}} with a degree d i {\displaystyle d_{i}} specified for each vertex i {\displaystyle i} is equal to the multinomial coefficient ( n − 2 d 1 − 1 , d 2 − 1 , … , d n − 1 ) = ( n − 2 ) ! ( d 1 − 1 ) ! ( d 2 − 1 ) ! ⋯ ( d n − 1 ) ! . {\displaystyle {\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 {\displaystyle i} appears exactly d i − 1 {\textstyle 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 G is the complete bipartite graph with vertices 1 to n1 in one partition and vertices n1 + 1 to n in the other partition, the number of labeled spanning trees of G is n 1 n 2 − 1 n 2 n 1 − 1 {\displaystyle n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}}, where n2 = n − n1.
  • 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