• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Deutsch (DE)
Deutsch (UK)
Deutsch (US)

Americas

Europe

Answers without the blur. Sign up and see all textbooks for free! → Illustration

Q44E

Expert-verified
Discrete Mathematics and its Applications
Found in: Page 757
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Register for Free I’ll do it later
Illustration

Short Answer

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.

Color the root of the tree Blue. Next, color all vertices at level 1 Red, all vertices at level 2 Blue, all vertices at level 3 red, and so on.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :
TABLE OF CONTENTS

Step 1: Definition

A tree is an undirected graph that is connected and that does not contain any simple circuits.

The level of a vertex is the length of the path from the root to the vertex.

Step 2: Assuming color to the trees

To prove: Every tree can be colored using two colors.

Let us use the two colors Red and Blue. Color the root of the tree Blue. Next, color all vertices at level 1 Red, all vertices at level 2 Blue, all vertices at level 3 Red, and so on.

Since a vertex v at level h can only be directly connected to a vertex at level h-1 or at level h+1, the vertex v always has a different color than the vertices it is connected to (as they are in the previous and the following level).

Most popular questions for Math Textbooks

In Exercises 2–6 find a spanning tree for the graph shown by removing edges in simple circuits.

a) What is a binary search tree?

b) Describe an algorithm for constructing a binary search tree.

c) Form a binary search tree for the words, vireo, warbler, egret, grosbeak, nuthatch, and kingfisher.

How many nonisomorphic rooted trees are there with six vertices?

Suppose that \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\) are n positive integers with sum \({\bf{2n - 2}}\). Show that there is a tree that has n vertices such that the degrees of these vertices are \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\).

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.
Icon

Want to see more solutions like these?

Sign up for free to discover our expert answers
Get Started - It’s free

Recommended explanations on Math Textbooks

Decision Maths

Read explanation

Calculus

Read explanation

Probability and Statistics

Read explanation

Statistics

Read explanation

Mechanics Maths

Read explanation

Geometry

Read explanation

Pure Maths

Read explanation

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.