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 . 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
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
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(''a'')
1 ''n'' ← ''length'' 'a'' 2 ''T'' ← a graph with ''n'' + 2 isolated nodes, numbered 1 to ''n'' + 2
3 ''degree'' ← an array of integers
4 for each node ''i'' in ''T'' do
5 ''degree'' 'i''← 1
6 for each value ''i'' in ''a'' do
7 ''degree'' 'i''← ''degree'' 'i''+ 1
Next, for each number in the sequence a /code>, find the first (lowest-numbered) node, j
, with degree equal to 1, add the edge (j, a
to the tree, and decrement the degrees of j
and a /code>. In pseudo-code:
8 for each value ''i'' in ''a'' do
9 for each node ''j'' in ''T'' do
10 if ''degree'' 'j''= 1 then
11 Insert ''edge'' 'i'', ''j''into ''T''
12 ''degree'' 'i''← ''degree'' 'i''- 1
13 ''degree'' 'j''← ''degree'' 'j''- 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 ''u'' ← ''v'' ← 0
16 for each node ''i'' in ''T''
17 if ''degree'' 'i''= 1 then
18 if ''u'' = 0 then
19 ''u'' ← ''i''
20 else
21 ''v'' ← ''i''
22 break
23 Insert ''edge'' 'u'', ''v''into ''T''
24 ''degree'' 'u''← ''degree'' 'u''- 1
25 ''degree'' 'v''← ''degree'' 'v''- 1
26 return ''T''
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 ''n''''n''−2, so the existence of this bijection proves Cayley's formula
In mathematics, Cayley's formula is a result in graph theory named after Arthur Cayley. It states that for every positive integer n, the number of trees on n labeled vertices is n^.
The formula equivalently counts the number of spanning tr ...
, i.e. that there are
''n''''n''−2 labeled trees on ''n'' vertices.
* Cayley's formula can be strengthened to prove the following claim:
:The number of spanning trees in a complete graph with a degree specified for each vertex is equal to the multinomial coefficient
In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.
Theorem
For any positive integer ...
::
:The proof follows by observing that in the Prüfer sequence number appears exactly times.
* Cayley's formula can be generalized: a labeled tree is in fact a spanning tree of the labeled complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
. 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 , where ''n''2 = ''n'' − ''n''1.
* 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.
References
External links
Prüfer code
– from MathWorld
''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Di ...
{{DEFAULTSORT:Prufer Sequence
Enumerative combinatorics
Trees (graph theory)