Prefer Code
The trees. Briefly recall
A tree is a special case of a graph. Trees are widely used in programming. A tree is a connected graph without cycles. A tree is called tagged if each vertex has a unique label. This is usually a number.
Definition Constructing a Prufer code for a given tree
The Prufer code is a one-to-one encoding of labeled trees with n vertices using a sequence of n-2 integers in the interval [1, n]. That is, we can say that the Prüfer code is a bijection between all spanning trees of a complete graph and numerical sequences.
This method of encoding trees was proposed by the German mathematician Heinz Prüfer in 1918.
Consider the algorithm for constructing the Prüfer code for a given tree with n vertices.
A list of edges is fed to the input. The leaf of the tree with the lowest number is selected, then it is removed from the tree, and the vertex number that was associated with this leaf is added to the Prüfer code. This procedure is repeated n-2 times. In the end, only 2 vertices remain in the tree, and the algorithm completes. The numbers of the remaining two vertices are not written to the code.
Thus, the Prüfer code for a given tree is a sequence of n-2 numbers, where each number is the number of the vertex associated with the smallest leaf at that time - that is, this number in the interval [1, n].
Example 
Source tree 
Prufer code: 1 
Prufer code: 1 5 
Prufer code: 1 5 2 
Prufer code: 1 5 2 6 
Prufer code: 1 5 2 6 6 
Prufer code: 1 5 2 6 6 2 
Prufer code: 1 5 2 6 6 2 1 
Prufer Code: 1 5 2 6 6 2 1 3
Recovering a tree by its Prefer code
Next to the task of constructing the Prüfer code is the task of restoring the encoded tree. We will consider a tree restoration algorithm with the following conditions: a sequence of digits (vertices), which represents the Prufer code, is input, the result is a list of tree edges. Thus, the problem will be solved.
Consider the decoding algorithm in detail. In addition to the code, we need a list of all the vertices of the graph. We know that the Prufer code consists of n-2 vertices, where n is the number of vertices in the graph. That is, we can determine the number of vertices in the encoded tree by the size of the code.
As a result, at the beginning of the algorithm we have an array of n-2 Prüfer code and an array of all vertices of the graph: [1 ... n]. Next, such a procedure is repeated n-2 times: the first element of the array containing the Prüfer code is taken, and the array with the vertices of the tree is searched for the smallest vertex not contained in the array with the code. The found vertex and the current element of the array with the Prüfer code make up the edge of the tree. The vertex data is deleted from the corresponding arrays, and the procedure described above is repeated until the elements in the array with the code run out. At the end of the algorithm, two vertices remain in the array with the vertices of the graph; they make up the last edge of the tree. As a result, we get a list of all edges of the graph that has been encoded.
Example We will
restore the tree using the Prüfer code, which was obtained in the encoding example.
The first step is the
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 4
List of edges: 1 4
Second step.
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 7
List of edges: 1 4, 5 7
The third step.
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 5
List of edges: 1 4, 5 7, 2 5
Fourth step.
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 8
List of edges: 1 4, 5 7, 2 5, 6 8
Fifth step.
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 9
List of edges: 1 4, 5 7, 2 5, 6 8, 6 9
Sixth step.
Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 6
List of edges: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6
Seventh step.
Prufer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prufer code is 2
List of edges: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2
The eighth step.
The Prefer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prefer code is 1
List of edges: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1
Completion of the algorithm.
Prufer code: 1 5 2 6 6 2 1 3
Array of tree vertices: 1 2 3 4 5 6 7 8 9 10
The minimum vertex not contained in the Prufer code is 1
List of edges: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1, 3 10
Conclusion
Prufer's code was proposed as a clear and simple proof of Cayley's formula for the number of marked trees. In practice, it is used more often to solve combinatorial problems.
Sources
- Wilson R. Introduction to Graph Theory. Translation from English M .: Mir, 1977. -208 p.
- Combinatorics. Boolean functions. Counts: textbook. manual / A. A. Balagura, O. V. Kuzmin. - Irkutsk: Publishing house of the ISU, 2012 .-- 115 p.
- MAXimal [Electronic resource] - Access mode: link , free. (Date of treatment: 04/22/2017)
