Question

Use breadth-first search to find a spanning tree of each of the graphs in Exercise 17.

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

Solution for\({{\bf{W}}_{\bf{6}}}\).

Here \({{\bf{W}}_{\bf{6}}}\)is a cycle \({{\bf{C}}_{\bf{6}}}\)with an additional vertex that is connected to all other vertices.

Let the 7 vertices are a,b,c,d,e,f,g with a the vertex connected to all other vertices.

Starts form vertex a. So, path =a.

And a is adjacent to the b,c,d,e,f,g. Thus we can draw the edges from a to all other vertex.

The spanning tree is

Result for \({{\bf{K}}_{\bf{5}}}\).

Here \({{\bf{K}}_{\bf{5}}}\)has 5 vertices and edges between every pair of vertices.

Let the 5 vertices are a,b,c,d,e with a the vertex connected to all other vertices.

Starts form vertex a.So path=a.

And a is adjacent to the b,c,d,e.Thus we can draw the edges from a to all other vertex.

The spanning tree is

Find the result of \({{\bf{K}}_{{\bf{3,4}}}}\).

Here \({{\bf{K}}_{{\bf{3,4}}}}\)contains set of 3 vertices M=a,b,c and a set of 4 vertices N=d,e,f,g.

Every vertex in M is connected to vertex in N.

Starts form vertex a.

And a is adjacent to the d,e,f,g. Thus we can draw the edges from d,e,f,g.

Now d is adjacent to b,c,thus we can draw from d to b and c.

The spanning tree is

Find the spanning tree for \({{\bf{Q}}_{\bf{3}}}\).

Here \({{\bf{Q}}_{\bf{3}}}\)contains the bit strings of 3 vertices 000,001,011,100,101,110,111.

Vertices are connected if exactly one of the bits of the strings differ.

Starts form vertex 000.

And 000 is adjacent to the 001,010,100.Thus we can draw the edges from 000 to 001,010,100.

Now 001 is adjacent to 011,101.Thus can draw an edges from 001 to 011,101.

The next path 010 is adjacent to 110. Then draw an edges from 010 to 110.

101 is adjacent to 111. Thus draw an edge from 101 to 111.

The spanning tree is

This is the required result.