Prüfer sequence

<h2 id="algorithm-to-convert-a--tree-into-a-prfer-sequence">Algorithm to convert a tree into a Prüfer sequence</h2>
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 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h3>Example</h3>

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

<h2 id="algorithm-to-convert-a-prfer-sequence-into-a-tree">Algorithm to convert a Prüfer sequence into a tree</h2>
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(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[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 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.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

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

<h2 id="cayleys-formula">Cayley's formula</h2>
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 <a href="/facts/Bijection/j4gTuTmW">bijection</a> 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 nn−2, so the existence of this bijection proves <a href="/facts/Cayley%2527s_formula/fwjWPJTf">Cayley's formula</a>, i.e. that there are nn−2 labeled trees on n vertices.

<h2 id="other-applications">Other applications</h2>
Source:<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<ul><li>Cayley's formula can be strengthened to prove the following claim:</li></ul>
The number of spanning trees in a complete graph 
 
 
 
 
 K
 
 n
 
 
 
 
 {\displaystyle K_{n}}
 
 with a degree 
 
 
 
 
 d
 
 i
 
 
 
 
 {\displaystyle d_{i}}
 
 specified for each vertex 
 
 
 
 i
 
 
 {\displaystyle i}
 
 is equal to the <a href="/facts/Multinomial_coefficient/0kyhtHvf">multinomial coefficient</a>

(
            
            
              
                n
                −
                2
              
              
                
                  d
                  
                    1
                  
                
                −
                1
                ,
                
                
                  d
                  
                    2
                  
                
                −
                1
                ,
                
                …
                ,
                
                
                  d
                  
                    n
                  
                
                −
                1
              
            
            
              )
            
          
        
        =
        
          
            
              (
              n
              −
              2
              )
              !
            
            
              (
              
                d
                
                  1
                
              
              −
              1
              )
              !
              (
              
                d
                
                  2
                
              
              −
              1
              )
              !
              ⋯
              (
              
                d
                
                  n
                
              
              −
              1
              )
              !
            
          
        
        .
      
    
    {\displaystyle {\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\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
 
 
 {\displaystyle i}
 
 appears exactly 
 
 
 
 
 d
 
 i
 
 
 −
 1
 
 
 {\textstyle d_{i}-1}
 
 times.
<ul><li>Cayley's formula can be generalized: a labeled tree is in fact a <a href="/facts/Spanning_tree_(mathematics)/qQPN9taR">spanning tree</a> of the labeled <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a>. By placing restrictions on the enumerated Prüfer sequences, similar methods can give the number of spanning trees of a complete <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a>. If G is the complete bipartite graph with vertices 1 to n1 in one partition and vertices n1 + 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
 
 
 
 
 {\displaystyle n_{1}^{n_{2}-1}n_{2}^{n_{1}-1}}
 
, where n2 = n − n1.</li>
<li>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.</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://mathworld.wolfram.com/PrueferCode.html">Prüfer code</a> – from <a href="/facts/MathWorld/yc1jodbq">MathWorld</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Prüfer, H. (1918). "Neuer Beweis eines Satzes über Permutationen". Arch. Math. Phys. 27: 742–744. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Caminiti, S., Finocchi, I., Petreschi, R. (2007). "On coding labeled trees". Theoretical Computer Science. 382 (2): 97–108. doi:10.1016/j.tcs.2007.03.009.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="https://doi.org/10.1016%2Fj.tcs.2007.03.009" target="_blank">https://doi.org/10.1016%2Fj.tcs.2007.03.009</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Jens Gottlieb; Bryant A. Julstrom; Günther R. Raidl; Franz Rothlauf. (2001). "Prüfer numbers: A poor representation of spanning trees for evolutionary search" (PDF). Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001): 343–350. Archived from the original (PDF) on 2006-09-26. <a href="https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf" target="_blank">https://web.archive.org/web/20060926171652/http://www.ads.tuwien.ac.at/publications/bib/pdf/gottlieb-01.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Kajimoto, H. (2003). "An Extension of the Prüfer Code and Assembly of Connected Graphs from Their Blocks". Graphs and Combinatorics. 19 (2): 231–239. doi:10.1007/s00373-002-0499-3. S2CID 22970936. <a href="/wiki/Graphs_and_Combinatorics" target="_blank">/wiki/Graphs_and_Combinatorics</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Prüfer sequence open-in-new

Prüfer sequence