distance dans un graphe

distance dans un graphe

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 :