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: Q14E (page 795)

In Exercises 13–15 use depth-first search to produce a spanningtree for the given simple graph. Choose aas the root of this spanning tree and assume that the vertices are ordered alphabetically.

Short Answer

Expert verified

For the result follow the steps.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

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

01

Compare with the definition.

A spanning tree of a simple graph G is a subgraph of G that is a tree and that contains all vertices of G.

A tree is an undirected graph that is connected and does not contain any single circuit. And a tree with n vertices has n-1 edges.

02

Use depth-first search.

Starts from any randomly chosen root and then creates a path by successively adding vertices to the path that we adjacent to the previous vertex in the path and the vertex that is added can not be in the path.

Given is that the root of the spanning tree will be a.Thus a is the first vertex in the path.

And a is connected to the b and g. Since b occurs first so we add b first then path=a,b.

Now b is connected to c and g .but c comes first. Then path=a,b,c.

Apply the same procedure up to I. And the path is

Path=a,b,c,h,g,i

03

Second path.

Move back to the vertex g in the path.

Thus g is not adjacent to any vertices that not in the path.so we have to move vertex h.

Mow h is connected to I and m.So I come first so the path is =h,i.

Now, I is connected to d,e,j, n.d comes first so the path=h,I,d.

Apply the same procedure the path is h,I,d,e,f,k,j,n.

Since n is not connected to any vertices and is already in the path thus this is the second of the tree.

04

Third path of tree.

The last vertex in the second path that is adjacent to a vertex no contained in any path.

Now, I is the first vertex connected to m.Thus the third path is the from vertex I to vertex m. So the path is=I,m.

All vertices are contained in one of the tree path, thus the spanning tree contains all edges in one of the paths.

The spanning tree is

This is the required result.

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

Show that the average depth of a leaf in a binary tree with \(n\) vertices is \({\bf{\Omega (logn)}}\).

How many comparisons are needed to locate or to add each of the words in the search tree for Exercise 2, starting fresh each time?

a) palmistry

b) etymology

c) paleontology

d) glaciology

Show that every tree with at least one edge must have at least two pendant vertices.

Show that if no two edges in a weighted graph have the same weight, then the edge with least weight incident to a vertex v is included in every minimum spanning tree.

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.
See all solutions

Recommended explanations on Math Textbooks

Probability and Statistics

Read Explanation

Decision Maths

Read Explanation

Geometry

Read Explanation

Applied Mathematics

Read Explanation

Discrete Mathematics

Read Explanation

Mechanics 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