申論題

14. (20 points) A tree T is assumed to be simple, undirected, and with positive edge-weights. Let dr (u, ข) denote the distance between u and u on T. For a vertex u, the eccentricity of u is the maximum of the distance to any vertex in the tree, ie,, The diameter of a tree is the unaximum of the eccentricity of any vertex in the tree. (The term "diameter" is overloaded. It is defined as the maximum eccentricity and also as the path of length equal to the maximum eccentricity.) The radius of a tree is the minimum eccentricity among all vertices in the tree, and a center of a tree is a vertex with eccentricity equal to the radius.