centre d’un graphe

centre d’un graphe

Dans un graphe donné, le centre est le sommet dont l’écartement est minimal.

Un graphe peut évidemment avoir plusieurs centres.

L’écartement d’un centre du graphe s’appelle le rayon du graphe.

Exemple

Dans le graphe ci-dessous, puisque tous les sommets peuvent être reliés à n’importe quel autre par une chaine de deux arêtes, ils sont tous des centres du graphe et leur écartement est 2.  Le rayon de ce graphe est donc 2.