Labeled Tree from Prüfer Sequence

From ProofWiki
Jump to: navigation, search

Algorithm

Given a Prüfer sequence, it is possible to generate a finite labeled tree corresponding to that sequence.


Let $P = \left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$ be a Prüfer sequence. This will be called the sequence.

It is assumed the sequence is not empty.

Step 1: Draw the $n$ nodes of the tree we are to generate, and label them from $1$ to $n$. This will be called the tree.
Step 2: Make a list of all the integers $\left({1, 2, \ldots, n}\right)$. This will be called the list.
Step 3: If there are two numbers left in the list, connect them with an edge and then stop. Otherwise, continue on to step 4.
Step 4: Find the smallest number in the list which is not in the sequence, and also the first number in the the sequence. Add an edge to the tree connecting the nodes whose labels correspond to those numbers.
Step 5: Delete the first of those numbers from the list and the second from the sequence. This leaves a smaller list and a shorter sequence. Then return to step 3.


The above constitutes an algorithm, for the following reasons:


Finiteness

For each iteration through the algorithm, step 5 is executed, which reduces the size of the list by $1$.

Therefore, after $n-2$ iterations, at step 1 there will be $2$ numbers left in the list, and the algorithm will stop.


Definiteness

Steps 1 and 2: Trivially definite.
Step 3: We are starting with a non-empty Prüfer sequence of length $n-2$, so the list must originally contain at least $3$ elements. As the number of elements in the list decreases by $1$ each iteration (see step 5), eventually there is bound to be just two elements in the list.
Step 4: As there are more elements in the list than there are in the sequence, by the Pigeonhole Principle there has to be at least one number in the list that is not in the sequence.
Step 5: Trivially definite.


Inputs

The input to this algorithm is the Prüfer sequence $\left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$.


Outputs

The output to this algorithm is the tree $T$.

The fact that $T$ is in fact a tree follows from the fact that:

  • $T$ has $n$ nodes and (from the method of construction) $n-1$ edges;

So $T$ is a tree from Equivalent Definitions for Finite Tree.


Effective

Each step of the algorithm is basic enough to be done exactly and in a finite length of time.


Example

Let the starting Prüfer sequence be $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.


Step 1: The sequence is length $6$, so the tree will have $8$ nodes:
PruferSequenceExample2-T-0.png


Step 2: We generate the list: $\left({1, 2, 3, 4, 5, 6, 7, 8}\right)$.


Iteration 1

Step 3: There are $8$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $2$, and the first number in the sequence is $1$. We join $1$ and $2$, to obtain this graph:
PruferSequenceExample2-T-1.png
Step 5: We delete $2$ from the list to obtain $\left({1, 3, 4, 5, 6, 7, 8}\right)$, and $1$ from the start of the sequence to obtain $\left({\mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.


Iteration 2

Step 3: There are $7$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $3$, and the first number in the sequence is $7$. We join $3$ and $7$, to obtain this graph:
PruferSequenceExample2-T-2.png
Step 5: We delete $3$ from the list to obtain $\left({1, 4, 5, 6, 7, 8}\right)$, and $7$ from the start of the sequence to obtain $\left({\mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.


Iteration 3

Step 3: There are $6$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $4$, and the first number in the sequence is $5$. We join $4$ and $5$, to obtain this graph:
PruferSequenceExample2-T-3.png
Step 5: We delete $4$ from the list to obtain $\left({1, 5, 6, 7, 8}\right)$, and $5$ from the start of the sequence to obtain $\left({\mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.


Iteration 4

Step 3: There are $5$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $5$, and the first number in the sequence is $7$. We join $5$ and $7$, to obtain this graph:
PruferSequenceExample2-T-4.png
Step 5: We delete $5$ from the list to obtain $\left({1, 6, 7, 8}\right)$, and $7$ from the start of the sequence to obtain $\left({\mathbf{7}, \mathbf{1}}\right)$.


Iteration 5

Step 3: There are $4$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $6$, and the first number in the sequence is $7$. We join $6$ and $7$, to obtain this graph:
PruferSequenceExample2-T-5.png
Step 5: We delete $6$ from the list to obtain $\left({1, 7, 8}\right)$, and $7$ from the start of the sequence to obtain $\left({\mathbf{1}}\right)$.


Iteration 6

Step 3: There are $3$ elements in the list, so we move on to step 4.
Step 4: The smallest number in the list which is not in the sequence is $7$, and the first number in the sequence is $1$. We join $7$ and $1$, to obtain this graph:
PruferSequenceExample2-T-6.png
Step 5: We delete $7$ from the list to obtain $\left({1, 8}\right)$, and $1$ from the start of the sequence, which is at this point empty.


Iteration 7

Step 3: There are $2$ elements in the list: $\left({1, 8}\right)$, so we join them to obtain this graph:
PruferSequenceExample2-T-7.png

Then we stop.


The algorithm has terminated, and the tree is complete.

Rearranging the positions of the nodes, we can draw it like this:

PruferSequenceExample-T-0.png


Also see

Compare with the example given in Prüfer Sequence from Labeled Tree.

These two results are pulled together in Bijection between Prüfer Sequences and Labeled Trees.