La notion de graphe est une structure combinatoire permettant de
représenter de nombreuses situations rencontrées dans des
applications faisant intervenir des mathématiques discrètes et
nécessitant une solution informatique. Circuits électriques,
réseaux de transport (ferrés, routiers, aériens), réseaux
d'ordinateurs, ordonnancement d'un ensemble de tâches sont les
principaux domaines d'application où la structure de graphe
intervient. D'un point de vue formel, il s'agit d'un ensemble de
points (sommets) et d'un ensemble d'arcs reliants des couples de
sommets. Une des premières questions que l'on se pose est de
déterminer, étant donné un graphe et deux de ses sommets, s'il
existe un chemin (suite d'arcs) qui les relie; cette question très
simple d'un point de vue mathématique pose des problèmes
d'efficacité dès que l'on souhaite la traiter à l'aide de
l'ordinateur pour des graphes comportant un très grand nombre de
sommets et d'arcs. Pour se convaincre de la difficulté du problème
il suffit de considérer le jeu d'échecs et représenter chaque
configuration de pièces sur l'échiquier comme un sommet d'un
graphe, les arcs joignent chaque configuration à celles obtenues par
un mouvement d'une seule pièce; la résolution d'un problème
d'échecs revient ainsi à trouver un ensemble de chemins menant
d'un sommet à des configurations de ``mat''. La difficulté
du jeu d'échecs provient donc de la quantité importante de sommets
du graphe que l'on doit parcourir. Des graphes plus simples comme
celui des stations du Métro Parisien donnent lieu à des
problèmes de parcours beaucoup plus facilement solubles.
Il est courant, lorsque l'on étudie les graphes, de distinguer entre
les graphes orientés dans lesquels les arcs doivent être parcourus
dans un sens déterminé (de 
vers 
mais pas de vers )
et les graphes symétriques (ou non orientés) dans lesquels les
arcs (appelés alors arêtes) peuvent être parcourus dans les deux
sens. Nous nous limitons dans ce chapitre aux graphes orientés, car
les algorithmes de parcours pour les graphes orientés s'appliquent
en particulier aux graphes symétriques : il suffit de construire à
partir d'un graphe symétrique 
le graphe orienté 
comportant pour chaque arête 
de deux arcs opposés, l'un
de vers et l'autre de vers .