Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Saturday, April 20, 2024, 9:40 AM

Description

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

Table of contents

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.

Solutions

  1. Answer:

    \begin{matrix} k & 1 & 2 & 3 & 4 & 5 & 6\\ V[k].\mathrm{found} & T & T & T & F & F & T\\ V[k].\mathrm{from} & 2 & 5 & 6 & * & * & 5\\ \mathrm{DepthSet} & 2 & 1 & 2 & * & * & 1 \end{matrix}

    * = undefined

  2. Answer: If the number of vertices is n, there can be \frac{(n-1)(n-2)}{2} vertices with one vertex not connected to any of the others. One more edge and connectivity is assured.

  3. Answer:
    1. The eccentricity of each vertex is 2; and the diameter and radius are both 2 as well. All vertices are part of the center.
    2. The corners (1, 3, 10, and 10) have eccentricities 5. The two central vertices, 5 and 8, which are in the center of the graph have eccentricity 3. All other vertices have eccentricity 4. The diameter is 5. The radius is 3.
    3. Vertices 1, 2, and 5 have eccentricity 2 and make up the center of this graph. Vertices 7 and 8 have eccentricity 4, and all other vertices have eccentricity 3. The diameter is 4. The radius is 2.
    4. The eccentricity of each vertex is 4; and the diameter and radius are both 4 as well. All vertices are part of the center.