Question

Describe the trees produced by breadth-first search anddepth-first search of the complete bipartite graph \({{\bf{K}}_{{\bf{m,n}}}}\), starting at a vertex of degree m, where m and n are positive integers. Justify your answers.

Short answer

For the result follow the steps.

Step-by-step solution

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.

Use breadth first search method.

Consider a complete bipartite graph \({{\bf{K}}_{{\bf{m,n}}}}\) with vertex set \({\bf{(}}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{u}}_{\bf{2}}}{\bf{,}}....{{\bf{u}}_{\bf{m}}}{\bf{)}}\) and \({\bf{(}}{{\bf{v}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{2}}}{\bf{,}}....{{\bf{v}}_{\bf{n}}}{\bf{)}}\).Using breadth first search algorithm and choosing vertices alphabetically ,if we start at \({{\bf{v}}_{\bf{1}}}\) as the root of the spanning tree then at level 1 there will be all the vertices of the half of the bipartition \({\bf{(}}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{u}}_{\bf{2}}}{\bf{,}}....{{\bf{u}}_{\bf{m}}}{\bf{)}}\) ,because they are the only neighbors \({{\bf{v}}_{\bf{1}}}\) of who are no so pairwise among themselves. Choose and all the remaining vertices of the other bipartition are neighbors of \({{\bf{u}}_{\bf{1}}}\) any edges between \({{\bf{v}}_{\bf{i}}}{\bf{,}}{{\bf{v}}_{\bf{j}}}\) .

Hence, they are the children of at level 2 as well as the leaves of the tree.

Use depth first search method.

Using depth first search algorithm, the spanning tree of \({{\bf{K}}_{{\bf{m,n}}}}\) starts at the root and then the next child \({{\bf{u}}_{\bf{1}}}\) is, who has a child in \({{\bf{v}}_{\bf{2}}}\) which in turn has only child \({{\bf{u}}_{\bf{2}}}\) and so on. This process continues until either of the bipartition is exhausted. If \({\bf{m = n}}\), the only leaf will be \({{\bf{u}}_{\bf{m}}}\). For the case \({\bf{n < m}}\), the leaves of the trees as well as the children of \({{\bf{v}}_{\bf{n}}}\) will be \({\bf{(}}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{u}}_{\bf{2}}}{\bf{,}}....{{\bf{u}}_{\bf{m}}}{\bf{)}}\) and the case \({\bf{n > m}}\) can be as likewise figured.

Therefore, this is the required result.