Solved: TEAM PROJECT. Center of a Graph and Related

Chapter 23, Problem 23.1.89

(choose chapter or problem)

TEAM PROJECT. Center of a Graph and Related Concepts. (a) Distance, eccentricity. Call the length of a shortest path u ~ v in a graph C = (V. E) the distance d(u, v) from II to v. For fixed u, call the greatest 1(11. u) as u ranges over V the ecce1ltricity E(II) of u. Find the eccentricity of vertices I, 2, 3 in the graph in Prob. 7. (b) Diameter, radius, center. The diameter d(C) ofa graph C = (V, E) is the maximum of li(li. u) as u andu vary over V. and the radius r(C) is the smallesteccentricity E(V) of the vertices v. A vertex v withE(V) = r(C) is called a ce1ltral rertex. The set of allcentral vertices is called the center of C. Find d(C),r(C) and the center of the graph in Prob. 7.(c) What are the diameter, radius, and center of thespanning tree in Example I?(d) Explain how the idea of a center can be used insetting up an emergency service facility on atransportation network. In setting up a fire station. ashopping center. How would you generalize theconcepts in the case of two or more such facilities?(e) Show that a tree T whose edges all have length Ihas center consisting of either one vertex or twoadjacent vel1ices.<0 Set up an algorithm of complexity 0(11) for findingthe center of a tree T