Chemin (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Chemin (graphe))
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie 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 à .

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.

Article détaillé : Problèmes de cheminement.

Références[modifier | modifier le code]

  1. Lucas Létocart, « Algorithmique de graphes » [PDF]

Articles connexes[modifier | modifier le code]