Chemin (théorie des graphes)
Dans un graphe orienté, un chemin d'origine et d'extrémité , noté [1], est défini par une suite finie d'arcs consécutifs, reliant à .
Pour les articles homonymes, voir Chemin (homonymie).
La notion correspondante dans les graphes non orientés est celle de chaîne.
Vocabulaire
Un chemin élémentaire est un chemin ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts.
Un chemin simple est un chemin ne passant pas deux fois par un même arc, c'est-à-dire dont tous les arcs sont distincts.
Un circuit est un chemin dont les deux extrémités sont identiques.
La longueur d'un chemin est le nombre d'arêtes du chemin, ou bien, dans le cas d'un graphe pondéré, la somme des poids des arêtes.
Recherche de chemin
L'existence d'un chemin d'un sommet à un autre peut être testée à l'aide d'un parcours de graphe, par exemple un parcours en profondeur ou un parcours en largeur. Dans un graphe pondéré avec des poids positifs, l'algorithme de Dijkstra permet de trouver un plus court chemin.
Références
- Lucas Létocart, « Algorithmique de graphes » [PDF]
Articles connexes
Portail de l'informatique théorique