申論題

12. Given a connected and weighted graph G = (V, E), where all the edge weights are positive integers. The eccentricity is the greatest shortest path distance between v and any other vertex. That is, , where d(v,u) denotes the shortest path distance between vertices v and u. For example, in the following figure, = max{d[b,a],d(b,c),d(b,d)} =9. Please answer the following questions.

(a) (3 points) A center of a graph is a vertex that incurs the minimum eccentricity. That is, a center c is defined as:. Is it possible for a graph to have more than one center? If yes, please provide an example; If no, please provide a proof.