Question

Use breadth-first search to produce a spanning tree foreach of the simple graphs in Exercises 13–15. Choose aas the root of each spanning tree.

Short answer

For the result follow the steps.

Step-by-step solution

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 that does not contain any single circuit. And a tree with n vertices has n-1 edges.

method for finding breadth first search.

First choose a root. Add all edges incident to the root. Then each of the vertices at level 1, add all edges incident with ta vertex not included in the tree yet. And repeat until all vertices were added to the tree.

Solve for question 13.

Starts from vertex a.Add the edges b and then add the edges c to the adjacent vertex d( that is not included in the tree yet).

Now add edges from d to its adjacent vertices e and f.

Repeat until all vertices were added to the spanning tree.

The spanning tree is

Solution for question 14.

Starts from vertex a.Add the edges b and g.Then add the edges b to the adjacent vertex c ( that is not included in the tree yet).

Now add edges from g to h and from g to l.

Repeat until all vertices were added to the spanning tree.

The spanning tree is

Result for question 15.

Starts from vertex a.Add the edges b and c.Then add the edges b to the adjacent vertex c and f(that is not included in the tree yet).

Now add edges from e to j.

Repeat until all vertices were added to the spanning tree.

The spanning tree is

This is the required result.