Parcours eulériens et hamiltoniens
L’étude des problèmes eulériens – ou hamiltoniens – (recherche d’une chaîne ou d’un cycle passant exactement une fois par chaque arête – ou par chaque sommet
– remonte aux origines de la théorie des graphes.
L’intérêt porté aujourd’hui à ces problèmes s’explique par leurs nombreuses applications : tournées de distribution, tracé automatique sur ordinateur, problèmes d’ordonnancement d’atelier, etc.
Chaînes et cycles eulériens
Il s’agit là d’une généralisation du jeu bien connu consistant à dessiner toutes les arêtes d’un graphe avec un crayon sans jamais le soulever, ni passer deux fois sur la même arête.
Soit G = (X; U) un graphe orienté.
Chaîne eulérienne. Une chaîne eulérienne est une chaîne empruntant une fois et une fois seulement chaque arc de G.
Cycle eulérien. Un cycle eulérien est une chaîne eulérienne dont les extrémités coïncident.
Un graphe possédant un cycle eulérien est appelé graphe eulérien.
Le problème de l’existence et de la détermination d’un cycle eulérien (d’une chaîne eulérienne) dans un graphe non orienté a été posé la première fois et résolu par Euler en 1736 à propos du célèbre problème des ponts de Konigsberg. Euler prouva l’impossibilité de l’obtention d’une solution en démontrant le théorème suivant :
Théorème 1
a) Un graphe non orienté connexe possède une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est égal à 0 ou 2.
b) Un graphe non orienté connexe admet cycle eulérien si et seulement si tous ses sommets ont un degré pair.
Exemple :
Le problème des sept ponts de Konigsberg peut maintenant être posé en ces termes : existe-t-il une chaîne ou un cycle eulérien dans le graphe suivant..
Sommaire
1 Éléments de théorie des graphes
1. La notion de graphe
2. Parcours eulériens et hamiltoniens
3. Coloration des sommets d’un graphe
2 Décomposition des graphes
1. Introduction
2. Décomposition basée sur la matrice d’adjacence
3. Décomposition basée sur la matrice de la fermeture transitive
4. Application aux arcs
3 Problèmes d’ordonnancement
1. Introduction
2. Modélisation par un graphe orienté
3. Construction du graphe PERT
4. Résolution du graphe PERT
5. Diagramme Gantt
4 Problème du plus court chemin
1. Introduction
2. Algorithme de Ford
3. Algorithme de Bellman
4. Algorithme de Dijkstra
