Question

In Exercises 1 – 3 construct the universal address system for the given ordered rooted tree. Then use this to order its vertices using the lexicographic order of their labels.

Short answer

Therefore, the labelled tree is shown below and its lexicographic order is \({\bf{0 < 1 < 1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1}}{\bf{.2 < 1}}{\bf{.1}}{\bf{.2 < 1}}{\bf{.2 < 2}}\).

Step-by-step solution

General form

Universal address system:

1. Label the roots with the integer 0. Then label its k children (at level 1) from left to right with 1, 2, 3, …, k.
2. For each vertex v at level n with label A, label its \({{\bf{k}}_{\bf{v}}}\) children, as they are drawn from left to right, with \({\bf{A}}{\bf{.1,A}}{\bf{.2,}}...{\bf{,A}}{\bf{.}}{{\bf{k}}_{\bf{v}}}\).

Lexicographic ordering: the vertex labelled \({{\bf{x}}_{\bf{1}}}{\bf{.}}{{\bf{x}}_{\bf{2}}}.....{{\bf{x}}_{\bf{n}}}\) is less than the vertex labelled \({{\bf{y}}_{\bf{1}}}{\bf{.}}{{\bf{y}}_{\bf{2}}}.....{{\bf{y}}_{\bf{m}}}\) if there is an \({\bf{i,0}} \le {\bf{i}} \le {\bf{n}}\), with \({{\bf{x}}_{\bf{1}}}{\bf{ = }}{{\bf{y}}_{\bf{1}}}{\bf{,}}{{\bf{x}}_{\bf{2}}}{\bf{ = }}{{\bf{y}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{x}}_{{\bf{i - 1}}}}{\bf{ = }}{{\bf{y}}_{{\bf{i - 1}}}}\), and \({{\bf{x}}_{\bf{i}}}{\bf{ < }}{{\bf{y}}_{\bf{i}}}\); or if \({\bf{n < m}}\) and \({{\bf{x}}_{\bf{i}}}{\bf{ = }}{{\bf{y}}_{\bf{i}}}\) for \({\bf{i = 1,2,}}...{\bf{,n}}\).

Evaluate the given rooted tree

Given that, the rooted tree.

Label the root of the tree as 0.

Then, the children of the roots are labelled as 1, 2, 3, … from left to right. And the children of the vertex are labelled as A.1, A.2, A.3, … from left to right.

Label the tree and use the lexicographic order of the labelled tree

The labelled tree is shown below.

Then, the lexicographic order of the labelled tree is \({\bf{0 < 1 < 1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1}}{\bf{.1 < 1}}{\bf{.1}}{\bf{.1}}{\bf{.2 < 1}}{\bf{.1}}{\bf{.2 < 1}}{\bf{.2 < 2}}\).