Graphes hamiltoniens

On dit qu'un graphe est hamiltonien s'il est possible de trouver un cycle passant une et une seule fois par tous les sommets.
On dit qu'un graphe est semi-hamiltonien s'il est possible de trouver une chaîne passant une et une seule fois par tous les sommets.

Contrairement aux graphes eulériens, il n'existe pas de caractérisation simple des graphes hamiltoniens ou semi-hamiltoniens. On peut cependant énoncer quelques propriétés et conditions suffisantes.

Théorème 2 (Ore)

Soit G = (V, E) un graphe simple d'ordre n 3. Si pour toute paire {x,y} de sommets non adjacents, on a d(x) + d(y) n, alors G est hamiltonien.

Corollaire (Dirac)

Soit G = (V, E) un graphe simple d'ordre n 3. Si pour tout sommet x de G, on a d(x) n/2, alors G est hamiltonien.
En effet, un tel graphe vérifie les conditions du théorème précédent. Si x et y ne sont pas adjacents, on a bien :

d(x) + d(y) n/2 + n/2 = n

Problème du voyageur de commerce

Le problème du voyageur de commerce (Traveling Salesman Problem en anglais) consiste à trouver le plus court cycle passant par tous les sommets dans un graphe où les arêtes sont pondérées. On travaille souvent sur un graphe complet.

Exercices

Exercice 1
Dessinez un graphe d'ordre au moins 5 qui est...
  1. hamiltonien et eulérien
  2. hamiltonien et non eulérien
  3. non hamiltonien et eulérien
  4. non hamiltonien et non eulérien
Exercice 2 (sur Macintosh)

Téléchargez le programme Voyageur et utilisez-le pour voir quelques heuristiques classiques pour le problème du voyageur de commerce. Prenez une cinquantaine de sommets.

Exercice 3 (sur le web)

Utilisez les applets java proposées ci-dessous pour voir quelques heuristiques classiques pour traiter le problème du voyageur de commerce.

Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés!
Mot de passe :

Didier Müller, 6.3.03