Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Apply Algorithm 9.3.8 to find a path from 5 to 1 in Figure 9.3.11. What would be the final value of V? Assume that the terminal vertices in edge lists and elements of the depth sets are put into ascending order, as we assumed in Example 9.3.10.

  2. In a simple undirected graph with no self-loops, what is the maximum number of edges you can have, keeping the graph unconnected? What is the minimum number of edges that will assure that the graph is connected?

  3. For each of the following graphs, determine the eccentricities of each vertex, and the diameter, radius, and center of the graph.


 


Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.