Excentricité et centre d'un réseau

Excentricité et centre d'un réseau.

Dans un graphe non orienté connexe, l'excentricité d'un sommet $u$ est la plus grande distance (en nombre d'arêtes) entre $u$ et un autre sommet. Le centre est l'ensemble des sommets d'excentricité minimale ; le diamètre est la plus grande excentricité. On étudie le réseau de villages suivant, où l'on veut installer une caserne de pompiers au plus près de tous :

G = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
     "D": ["B"], "E": ["B", "F"], "F": ["C", "E", "G"], "G": ["F"]}

• Écrire une fonction excentricite(G, u) en s'appuyant sur la fonction distances_bfs du cours.
• Écrire une fonction centre_et_diametre(G) et l'appliquer à ce réseau. Où installer la caserne ?
• Quel est le coût de centre_et_diametre pour un graphe à $n$ sommets et $m$ arêtes ?