Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Prüfer sequence
Summary
In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918.
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 ith 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.
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(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).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.