Distances dans un graphe

sommets

Définitions

Les cercles numérotés représentent des sommets du graphe.
Certains sommets peuvent être reliés entre eux par des arêtes.
S'il y a une arête entre deux sommets, on dit qu'ils sont adjacents.
Le nombre minimum d'arêtes séparant deux sommets est la distance entre ces sommets.
La distance entre un sommet et le sommet le plus éloigné de lui est l'excentricité de ce sommet. Elle est indiquée sur le sommet.
La plus grande distance possible entre deux sommets du graphe est le diamètre du graphe. C'est l'excentricité maximale du graphe.
Un sommet d'excentricité maximale est au bord du graphe. Le bord est colorié en vert.
Un sommet d'excentricité minimale est un centre du graphe. Les centres sont coloriés en rouge.
L'excentricité des centres est le rayon du graphe.