Dans un graphe connexe ou une composante connexe d’un graphe non connexe, on appelle distance entre deux sommets le nombre minimum d’arêtes d’une chaine allant de l’un à l’autre.
De façon similaire, dans un graphe connexe orienté ou une composante connexe d’un graphe non connexe orienté, on appelle distance entre deux sommets le nombre minimum d’arcs d’un chemin allant de l’un à l’autre.
Exemple
Dans le graphe orienté ci-dessous, la distance entre les sommets 1 et 9 est 2.
Voir aussi :
- Écartement (ou excentricité) d’un sommet d’un graphe
- Centre d’un graphe
- Rayon d’un graphe
- Diamètre d’un graphe