chemin

chemin

Dans un graphe orienté, suite d’arcs consécutifs. Chaque arc de la suite a une extrémité en commun avec l’arc précédent et l’autre extrémité avec l’arc suivant.

Le nombre d’arcs d’un chemin détermine la longueur du chemin.

Le plus long chemin d’un graphe orienté est le diamètre de ce graphe.

Exemple

Dans le graphe orienté ci-dessous, le chemin formé dans l’ordre par les arcs acfdcfg, et h est un chemin de longueur 8.