Print this chapterPrint this chapter

Try It Now

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.