Chapter 11: Trees

For which graphs do depth-first search and breadth-first search produce identical spanning trees no matter which vertex is selected as the root of the tree? Justify your answer.

Show that a subgraph \({\bf{T = }}\left( {{\bf{V,F}}} \right)\) of the graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) is an arborescence of G rooted at r if and only if T contains r, T has no simple circuits, and for every vertex \({\bf{v}} \in {\bf{V}}\) other than r, \({\bf{de}}{{\bf{g}}^ - }\left( {\bf{v}} \right){\bf{ = 1}}\) in T.

How many vertices, leaves, and internal vertices does the rooted Fibonacci tree \({T_n}\) have, where \(n\) is a positive integer? What is its height?

Use Exercise 43 to prove that if G is a connected, simple graph with n vertices and G does not contain a simple path of length k then it contains at most \(\left( {{\bf{k - 1}}} \right){\bf{n}}\) edges.

Show that a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\) has an arborescence rooted at the vertex r if and only if for every vertex \({\bf{v}} \in {\bf{V}}\), there is a directed path from r to v.

What is wrong with the following “proof” using mathematical induction of the statement that every tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\). Basis step: Every tree with one vertex clearly has a path of length \(0\). Inductive step: Assume that a tree with \({\bf{n}}\) vertices has a path of length \({\bf{n - 1}}\), which has \({\bf{u}}\) as its terminal vertex. Add a vertex \({\bf{v}}\) and the edge from \({\bf{u}}\)to \({\bf{v}}\). The resulting tree has \({\bf{n + 1}}\) vertices and has a path of length \({\bf{n}}\). This completes the inductive step.

Use mathematical induction to prove that breadth-first search visits vertices in order of their level in the resulting spanning tree.

In this exercise we will develop an algorithm to find the strong components of a directed graph \({\bf{G = }}\left( {{\bf{V,E}}} \right)\). Recall that a vertex \({\bf{w}} \in {\bf{V}}\) is reachable from a vertex \({\bf{v}} \in {\bf{V}}\) if there is a directed path from v to w.

1. Explain how to use breadth-first search in the directed graph G to find all the vertices reachable from a vertex \({\bf{v}} \in {\bf{G}}\).
2. Explain how to use breadth-first search in \({{\bf{G}}^{{\bf{conv}}}}\) to find all the vertices from which a vertex \({\bf{v}} \in {\bf{G}}\) is reachable. (Recall that \({{\bf{G}}^{{\bf{conv}}}}\) is the directed graph obtained from G by reversing the direction of all its edges.)
3. Explain how to use part (a) and (b) to construct an algorithm that finds the strong components of a directed graph G, and explain why your algorithm is correct.

Use pseudocode to describe a variation of depth-first search that assigns the integer n to the nth vertex visited in the search. Show that this numbering corresponds to the numbering of the vertices created by a preorder traversal of the spanning tree.

Show that the average depth of a leaf in a binary tree with \(n\) vertices is \({\bf{\Omega (logn)}}\).