Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q1E (page 783)

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

Expert verified

Therefore, the labelled tree is shown below and its lexicographic order is \(0 < 1 < 1.1 < 1.2 < 2 < 3\).

Step by step solution

01

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 \({k_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 \({x_1}.{x_2}.....{x_n}\) is less than the vertex labelled \({y_1}.{y_2}.....{y_m}\) if there is an \(i,0 \le i \le n\), with \({x_1} = {y_1},{x_2} = {y_2},...,{x_{i - 1}} = {y_{i - 1}}\), and \({x_i} < {y_i}\); or if \(n < m\) and \({x_i} = {y_i}\) for \(i = 1,2,...,n\).

02

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.

03

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{.2 < 2 < 3}}\).

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Answer these questions about the rooted tree illustrated.

  1. Which vertex is the root\(?\)
  2. Which vertices are internal\(?\)
  3. Which vertices are leaves\(?\)
  4. Which vertices are children of \({\bf{j}}\)\(?\)
  5. Which vertex is the parent of \({\bf{h}}\)\(?\)
  6. Which vertices are siblings of \({\bf{o}}\)\(?\)
  7. Which vertices are ancestors of \({\bf{m}}\)\(?\)
  8. Which vertices are descendants of \({\bf{b}}\)\(?\)

Prove that the reverse-delete algorithm always producesa minimum spanning tree when given as input a weightedgraph with distinct edge weights. (Hint: Use Exercise \(33\).)

Show that a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

Show that every tree can be colored using two colors. The rooted Fibonacci trees \({\bf{Tn}}\) are defined recursively in the following way. \({\bf{T1}}\)and\({\bf{T}}2\) are both the rooted tree consisting of a single vertex, and for \({\bf{n = 3, 4,}}...{\bf{,}}\) the rooted tree \({\bf{Tn}}\) is constructed from a root with \({\bf{Tn - }}1\) as its left subtree and \({\bf{Tn - 2}}\) as its right subtree.
See all solutions

Recommended explanations on Math Textbooks

Logic and Functions

Read Explanation

Decision Maths

Read Explanation

Mechanics Maths

Read Explanation

Calculus

Read Explanation

Applied Mathematics

Read Explanation

Pure Maths

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free