12. Given a connected and weighted graph G = (V, E), where all the edge weightsare positive integers

問題詳情

12. Given a connected and weighted graph G = (V, E), where all the edge weightsare positive integers. The eccentricity

is the greatestshortest path distance between v and any other vertex. That is,

, where d(v,u) denotes the shortest path distancebetween 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 tohave more than one center? If yes, please provide an example; If no, pleaseprovide a proof.