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

Both coding and decoding can be reduced to integer radix sorting and parallelized.{{cite journal | author=Caminiti, S., Finocchi, I., Petreschi, R. | title= On coding labeled trees | journal=Theoretical Computer Science | year=2007 | volume=382 | issue= 2 | pages=97–108|doi=10.1016/j.tcs.2007.03.009| doi-access=free }}

File:Tree graph.svg

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].

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:

Convert-Prüfer-to-Tree({{mvar|a}})

1 {{mvar|n}} ← length[{{mvar|a}}]

2 {{mvar|T}} ← a graph with {{mvar|n}} + 2 isolated nodes, numbered 1 to {{mvar|n}} + 2

3 degree ← an array of integers

4 for each node {{mvar|i}} in {{mvar|T}} do

5 degree[{{mvar|i}}] ← 1

6 for each value {{mvar|i}} in {{mvar|a}} do

7 degree[{{mvar|i}}] ← degree[{{mvar|i}}] + 1

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:

8 for each value {{mvar|i}} in {{mvar|a}} do

9 for each node {{mvar|j}} in {{mvar|T}} do

10 if degree[{{mvar|j}}] = 1 then

11 Insert edge[{{mvar|i}}, {{mvar|j}}] into {{mvar|T}}

12 degree[{{mvar|i}}] ← degree[{{mvar|i}}] - 1

13 degree[{{mvar|j}}] ← degree[{{mvar|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.{{cite journal |author1=Jens Gottlieb |author2=Bryant A. Julstrom |author3=Günther R. Raidl |author4=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 |url-status=dead |archiveurl=https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf |archivedate=2006-09-26 }}

15 {{mvar|u}} ← {{mvar|v}} ← 0

16 for each node {{mvar|i}} in {{mvar|T}}

17 if degree[{{mvar|i}}] = 1 then

18 if {{mvar|u}} = 0 then

19 {{mvar|u}} ← {{mvar|i}}

20 else

21 {{mvar|v}} ← {{mvar|i}}

22 break

23 Insert edge[{{mvar|u}}, {{mvar|v}}] into {{mvar|T}}

24 degree[{{mvar|u}}] ← degree[{{mvar|u}}] - 1

25 degree[{{mvar|v}}] ← degree[{{mvar|v}}] - 1

26 return {{mvar|T}}

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

The immediate consequence is that Prüfer sequences provide a bijection between the set of labeled trees on {{mvar|n}} vertices and the set of sequences of length {{math|n − 2}} on the labels 1 to {{mvar|n}}. The latter set has size {{math|n{{isup|n−2}}}}, so the existence of this bijection proves Cayley's formula, i.e. that there are {{math|n{{isup|n−2}}}} labeled trees on {{mvar|n}} vertices.

Source:{{cite journal | author=Kajimoto, H. | title= An Extension of the Prüfer Code and Assembly of Connected Graphs from Their Blocks | journal=Graphs and Combinatorics | year=2003 | volume=19 | issue= 2 | pages=231–239|doi=10.1007/s00373-002-0499-3| s2cid= 22970936 }}

• Cayley's formula can be strengthened to prove the following claim:

:The number of spanning trees in a complete graph $K\_n$ with a degree $d\_i$ specified for each vertex $i$ is equal to the multinomial coefficient

::$\backslash binom\{n-2\}\{d\_1-1,\backslash ,d\_2-1,\backslash ,\backslash dots,\backslash ,d\_n-1\}=\backslash frac\{(n-2)!\}\{(d\_1-1)!(d\_2-1)!\backslash 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 {{mvar|G}} is the complete bipartite graph with vertices 1 to {{math|n{{sub|1}}}} in one partition and vertices {{math|n{{sub|1}} + 1}} to {{mvar|n}} in the other partition, the number of labeled spanning trees of {{mvar|G}} is $n\_1^\{n\_2-1\}\; n\_2^\{n\_1-1\}$, where {{math|1=n{{sub|2}} = n − n{{sub|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.

{{reflist}}

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

{{DEFAULTSORT:Prufer Sequence}}

Category:Enumerative combinatorics

Category:Trees (graph theory)