Question

Describe the tree produced by breadth-first search anddepth-first search for the n-cube graph\({{\bf{Q}}_{\bf{n}}}\), where n is a positive integer.

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.

Solve the question by both method.

Here \({{\bf{Q}}_{\bf{n}}}\) has \({{\bf{2}}^{\bf{n}}}\) vertices with an edges between two vertices that differ by 1 bit.

In depth first search the result in a path of length\({{\bf{2}}^{\bf{n}}}{\bf{ - 1}}\).

Consider an example \({{\bf{Q}}_{\bf{3}}}\)contains the bit string of length of 3 vertices 000,001,010,011,100,101,110,111. Vertices are connected if exactly one of the bits of the strings differ. The path 000,001,010,011,100,101,110,111 of length 7will then be found when using depth first search starting from vertex 000.

Breadth first search can be described recursively. If n=0, then\({{\bf{Q}}_{\bf{n}}}\)contains 1 vertex. \({{\bf{Q}}_{\bf{n}}}\)Then consists of two copies \({{\bf{Q}}_{{\bf{n - 1}}}}\).The tree\({{\bf{Q}}_{\bf{n}}}\) of is the tree of \({{\bf{Q}}_{{\bf{n - 1}}}}\) with an extra child for the root.

This is the required result.