Chemin (théorie des graphes)

Dans un graphe orienté, un chemin d'origine $x$ et d'extrémité $y$ , noté $\mu [x,y]$ [1], est défini par une suite finie d'arcs consécutifs, reliant $x$ à $y$ .

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.