Prüfer sequence

In combinatorial mathematics, the Prüfer sequence (or Prüfer code) 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. [cite journal | author=Prüfer, H. | title=Neuer Beweis eines Satzes über Permutationen | journal=Arch. Math. Phys. | year=1918 | volume=27 | pages=742–744]

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 sequence of a labeled tree is clearly unique and has length "n" − 2.

Example

Consider the above algorithm run on the simple example 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 4445.

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:

for (i = 1; i <= n + 2; n++) degree [i] = 1; for (i = 1; i <= n; n++) degree [a [i] ++;

Then, for each number in the sequence a [i] , find j, the first (lowest-numbered) node with degree 1 and add the edge (j, a [i] ) to the tree.Decrement the degrees of a [i] and j. In pseudo-code:

tree = empty; for (i = 1; i <= n; n++) { for (j = 1; degree [j] != 1; j++) ; tree += edge (j, a [i] ); degree [j] --; degree [a [i] --; }

At the end of this loop two degree-1 nodes will remain (call them u,v). Lastly, add the edge (u,v) to the tree. [cite journal | author=Jens Gottlieb, Bryant A. Julstrom, Günther R. Raidl, and Franz Rothlauf. | title=Prüfer numbers: A poor representation of spanning trees for evolutionary search | journal=Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001) | year=2001 | pages=343-350
url=http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf]

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" &mdash; this much is clear. Somewhat less obvious is the fact that for a given sequence "S" of length "n"&ndash;2 on the labels 1 to "n", there is a "unique" labeled tree whose Prüfer sequence is "S". This can be proved fairly easily by induction on "n".

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"&ndash;2 on the labels 1 to "n". The latter set has size "n"^"n"−2, so the existence of this bijection proves Cayley's formula, i.e. that there are "n"^"n"−2 labeled trees on "n" vertices.

Other applications

* Cayley's formula can be strengthened to prove the following claim: The number of spanning trees in a complete graph $K\_n$ with degrees $d\_1,\; d\_2,\; ldots,\; d\_n$ is equal to :$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 "G" is the complete bipartite graph with vertices 1 to "n"₁ in one partition and vertices "n"₁ + 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\}$, where "n"₂ = "n" − "n"₁.

References

External links

* [http://mathworld.wolfram.com/PrueferCode.html Prüfer code] – from MathWorld