Introduction :
Le graphe est une structure que l'on trouve dans la modélisation d'un grand nombre de situations très diverses (réseaux de transports et de communications, ordonnancement de tâches, relations entre personnes ou institutions, etc.). En fait, dès qu'intervient une relation binaire entre des objets d'un même ensemble on a une structure de graphe. De ce fait, de nombreux problèmes peuvent se ramener à des problèmes classiques de la théorie des graphes: recherche de chemins (à coût minimal), détection de cycles ( circuits), composantes connexes, flots maximaux, ….
- L'exemple le plus classique est la modélisation d'un réseau de communication: réseaux de routes représentés par une carte routière, réseaux de chemins de fer; liaison aérienne, réseaux de téléphone, réseaux électriques, réseaux d'alimentation en eau potable, réseaux d'informations dans une organisation,….
- Le problème central de l'ordonnancement des tâches: la réalisation d'un projet important ( construction d'un barrage, d'un immeuble, d'un avion, fonctionnement d'une chaîne de fabrication, simulation de vols d'un avion,….), nécessite une parfaite coordination des différentes cellules de travail pour éviter des pertes de temps coûteuses.
D'un point de vue formel, il s'agit d'un ensemble de points (sommets ou noeuds) et d'un ensemble d'arcs (arêtes) reliant des couples de sommets: relations entre sommets.