Prüfer sequence
In combinatorial mathematics, the Prüfer sequence 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
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 .Algorithm to convert a Prüfer sequence into a tree
Let, a,..., a
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, find the first node, j, with degree equal to 1, add the edge j and a. 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. Lastly, add the edge
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:
- 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, 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.