Sommaire

Chemins et graphes

Un chemin peut être vu comme un parcours dans un graphe. Les principaux algorithmes se basent donc sur la théorie des graphes.

1. Définition et concepts

Un graphe est un ensemble de nœuds ou sommets (qui peuvent représenter par exemple des villes) liés par des arcs, qui seraient alors des routes.

Voici un graphe qui représente des gares et les liens qui existent entre ces gares (en train, sans changement) :

images/03DP01.png

Les gares de G1 à G6 sont donc les nœuds. L’arc allant de G5 à G6 indique la présence d’un lien direct entre ces deux gares. Il est noté (G5, G6) ou (G6, G5) selon le sens voulu.

Par contre pour aller de G1 à G6, il n’y a pas de lien direct, il faudra passer par G4 ou G5 si on ne souhaite qu’un changement, ou par G2 puis G3 avec deux changements.

Un chemin permet de rejoindre différents sommets liés entre eux par des arcs. Ainsi, G1-G2-G3-G6 est un chemin de longueur 3 (la longueur est le nombre d’arcs suivis).

On parle de circuit lorsqu’on peut partir d’un nœud et y revenir. Ici, le graphe contient de nombreux circuits, comme G1-G4-G5-G1 ou G4-G5-G6-G4.

L’ordre d’un graphe correspond au nombre de sommets qu’il contient. Notre exemple contient 6 gares, il s’agit donc d’un graphe d’ordre 6.

Deux nœuds sont dits adjacents (ou voisins) s’il existe un lien permettant d’aller de l’un à l’autre. G5 est donc adjacent à ...