Lecture
The Prüfer code – is a way of biuniquely encoding labeled trees with n vertices by means of a sequence of n-2 integers in the range [1,n]. That is, one can say that the Prüfer code – is a bijection between all spanning trees of a complete graph and numeric sequences. This method of encoding trees was proposed by the German mathematician Heinz Prüfer in 1918. The Prüfer code maps an arbitrary finite tree with 
vertices to a sequence of 
numbers (from 
to ) with possible repetitions. The relationship between a tree with labeled vertices and the Prüfer code is one-to-one: each tree corresponds to a unique Prüfer code, with the vertex numbers mapped to the elements of the code sequence. Conversely, from a given code of numbers one can uniquely reconstruct a tree with vertices. The code was constructed by Heinz Prüfer while proving Cayley's formula in 1918.
Let 
be a tree with vertices numbered by the numbers 
. The construction of the Prüfer code of the tree T is carried out by successively removing vertices from the tree until only two vertices remain. At each step the leaf vertex with the smallest number is chosen, and the number of the single vertex to which it is connected is written into the code. As a result a sequence 
is formed, made up of the numbers , possibly with repetitions.
For the tree in the diagram, vertex 1 is the leaf vertex with the smallest number, so it is removed first, and 4 is written into the Prüfer code.
Vertices 2 and 3 are removed next, so 4 is added to the code two more times.
Vertex 4 has now become a leaf and has the smallest number, so it is removed, and 5 is added to the code.
Only two vertices remain, so the code is now complete, and the process stops.
As a result we get the Prüfer code (4,4,4,5).
To reconstruct the tree from the code 
let's prepare a list of vertex numbers 
. Let's choose the first number 
that does not occur in the code. Let's add an edge 
, after which we remove from 
and 
from 
.
We repeat the process until the code becomes empty. At this point the list contains exactly two numbers 
and . It remains to add the edge 
, and the tree is built.
— is the degree of the vertex with number 
, then occurs in the Prüfer code exactly (
) times. 
Let {a , a , ..., a[n]}be the Prüfer sequence:
The tree will have n+2nodes, numbered from 1to n+2. For each node set its degree equal to the number of times it appears in the sequence plus 1. For example, in pseudocode:
Prüfer-to-tree conversion ( a ) 1 n ← length [ a ] 2 T ← graph with n + 2 isolated nodes, numbered from 1 to n + 2 3 degree ← array of integers 4 for each node i in T - 5 degree [ i ] ← 1 6 for each value i in do 7 degree [ i ] ← degree [ i ] + 1
Then for each number in the sequence a[i]find the first (with the smallest number) node jwith degree equal to 1, add the edge (j, a[i])to the tree, and decrease the degrees of jand a[i]. In pseudocode:
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 there will remain two nodes with degree 1 (let's call them u, v). Finally, 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
0 #include
1 using namespace std;
2 void printTreeEdges(int prufer[], int m)
3 {
4 int vertices = m + 2;
5 int vertex_set[vertices];
6 for (int i=0; i
0 int main()
1 {
2 int prufer[] = {4, 1, 3, 4};
3 int n = sizeof(prufer)/sizeof(prufer );
4 printTreeEdges(prufer, n);
5 return 0;
6 }
with vertices equals 
. The proof follows from the fact that the Prüfer code gives a bijection between spanning trees and sequences of length of numbers.
— is the sequence of degrees of the tree, then the number of trees with such degrees equals the multinomial coefficient
Comments