Prüfer sequence

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"1 in one partition and vertices "n"1 + 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"2 = "n" − "n"1.

References

External links

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Prüfer group — In mathematics, specifically group theory, the Prüfer p group or the p quasicyclic group or p infin; group, Z( p infin;), for a prime number p is the unique torsion group in which every element has p p th roots.*The Prüfer p group may be… …   Wikipedia

  • Heinz Prüfer — Ernst Paul Heinz Prüfer (10 November 1896 7 April 1934) was an German mathematician, who worked on abelian groups, algebraic numbers, knot theory and Sturm Liouville theory. His advisor was Issai Schur. See also * Prüfer sequence (also known as… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Combinatorial proof — In mathematics, the term combinatorial proof is often used to mean either of two types of proof of an identity in enumerative combinatorics that either states that two sets of combinatorial configurations, depending on one or more parameters,… …   Wikipedia

  • Star (graph theory) — Star The star S7. (Some authors index this as S8.) Vertices k+1 Edges k …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Bijective proof — In combinatorics, bijective proof is a proof technique that finds a bijective function f : A → B between two sets A and B , thus proving that they have the same number of elements, | A | = | B |. One place the technique is useful is where we wish …   Wikipedia

  • Cayley's formula — 2^{2 2}=1 tree with 2 vertices,3^{3 2}=3 trees with 3 vertices and 4^{4 2}=16trees with 4 vertices.In mathematics, Cayley s formula is a result in graph theory named after Arthur Cayley. It states that if n is an integer bigger than 1, the number …   Wikipedia

  • Neanderthal — For other uses, see Neanderthal (disambiguation). Neanderthal Temporal range: Middle to Late Pleistocene 0.6–0.03 Ma …   Wikipedia

  • P-adic number — In mathematics, the p adic number systems were first described by Kurt Hensel in 1897 [cite journal | last = Hensel | first = Kurt | title = Über eine neue Begründung der Theorie der algebraischen Zahlen | journal =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”