Question

Describe the trees produced by breadth-first search anddepth-first search of the complete graph\({{\bf{K}}_{\bf{n}}}\), where n is a positive integer. Justify your answers.

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 and depth first search.

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

And

In depth first search starts from any random chosen root and then create 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 cannot be in the path.

Solve by an example.

Here \({{\bf{K}}_{\bf{n}}}\) has n vertices with an edges between every pair of vertex.

For depth search the result a path of length n-1.

Consider an example of a\({{\bf{K}}_5}\)has 5 vertices and an edgesbetween every pair of vertices.Let the 5 vertices are a,b,c,d,e. The path a,b,c,d,e of length 4 willthen be found using depth first search stating from vertex a.

Breadth first search will result in all edges being connected to the same vertex.which result in a star like pattern.

Spanning tree.

For depth first search

For breadth first tree

This is the required result.