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.

Short Answer

Find a minimum spanning tree of each of these graphs where the degree of each vertex in the spanning tree does not exceed 2.

Therefore, the resulting minimum spanning tree is given in the graph shown below.

2. Therefore, the resulting minimum spanning tree is given in the graph shown below.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: General form

Definition of tree: A tree is a connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Minimum spanning tree: A spanning tree with smallest possible sum of weights of its edges.

Step 2: (a) Evaluate the minimum spanning tree of the given graph

Given that, a graph is shown below.

Noticed that the edges with the smallest weight 1 are \(\left\{ {b,c} \right\}\) and \(\left\{ {b,d} \right\}\).

Since, both edges cannot be included, because we will need a degree of more than 2 to connect to a, f or e.

So, we can only include one of the edges.

For example, let us use \(\left\{ {b,c} \right\}\), then we will also have to use \(\left\{ {c,d} \right\}\) to connected to d.

Then we need to connect b to another vertex (a, e, or f). we shouldn’t connect b to f as the weight on \(\left\{ {b,c} \right\}\) is the largest weight of an edge incident to b. we can choose among the other two vertices.

For example, let us choose \(\left\{ {a,b} \right\}\).

At last, noticed that \(\left\{ {a,f} \right\}\) and \(\left\{ {e,f} \right\}\) have to be in the minimum spanning tree. Because the graph either connected or contains a vertex with degree more than 2.

The resulting minimum spanning tree is given in the graph shown below.

Conclusion: The above graph represents the possibility of spanning tree.

Step 3: (b) Evaluate the minimum spanning tree of the given graph

Given that, a graph is shown below.

Noticed that a is only connected t b, so \(\left\{ {a,b} \right\}\) has to be included in the graph.

Then, use at most one more edge incident to b.

We cannot use the edges with weight 1,4 and 5. Because we will require the use of three edges incident to g, to d, to e or to g.

We should use the edge of weight 2, which is \(\left\{ {b,c} \right\}\).

We cannot use any more edges incident to b. so, we have to include the edges \(\left\{ {c,d} \right\}\) and \(\left\{ {d,g} \right\}\).

Since, \(\left\{ {e,g} \right\}\) has a weight that is the sum of the weight of \(\left\{ {e,f} \right\}\) and \(\left\{ {f,g} \right\}\), we should include the two edges.

So, the resulting minimum spanning tree is given in the graph shown below.

Hence, the above graph represents the possibility of spanning tree.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Find a minimum spanning tree of each of these graphs where the degree of each vertex in the spanning tree does not exceed 2.

Step by Step Solution

Step 1: General form

Step 2: (a) Evaluate the minimum spanning tree of the given graph

Step 3: (b) Evaluate the minimum spanning tree of the given graph

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Find a minimum spanning tree of each of these graphs where the degree of each vertex in the spanning tree does not exceed 2.

Step by Step Solution

Step 1: General form

Step 2: (a) Evaluate the minimum spanning tree of the given graph

Step 3: (b) Evaluate the minimum spanning tree of the given graph

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths