StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q44SE

Expert-verifiedFound in: Page 805

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

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

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

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.

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.

94% of StudySmarter users get better grades.

Sign up for free