Chapitre 5 Hamiltonisme

Une question fameuse est de reconnaître les graphes finis (resp. graphes orientés finis) qui ont un cycle (resp. circuit orienté) hamiltonien, c'est-à-dire qui passe une fois et une seule par chaque sommet.

A l'origine, Hamilton avait essayé de vendre un jeu des 20 villes, où l'on cherchait un chemin hamiltonien sur une sphère avec la disposition suivante des villes et routes (étalée plus être plus visible dans la figure 5.1

Figure 5.1 : Le graphe de Hamilton

Une condition nécessaire évidente est que le graphe soit 2-connexe, (resp. que le graphe orienté soit fortement connexe).

À part le graphe de Cayley de

avec le générateur 1, les graphes de Cayley connexes passent le test.

En effet, si le graphe orienté fini est connexe, et s'il y a un arc de a à b, il y a un chemin orienté de b vers a: suivre les arcs provenant du même élément du groupe que l'arc (a,b). Par récurrence, on en déduit que s'il y a un chemin qui suit les arcs ou leurs opposés pour aller de a à b, on pourra construire un chemin orienté en remplaçant les arcs pris à l'envers par des chemins, et en court-circuitant au besoins les circuits qui ont pu apparaître.

Pour un graphe de Cayley non-orienté connexe fini à au moins 3 sommets, faisons un raisonnement par l'absurde. Le degré commun à tous les sommets est au moins 2, car le graphe est connexe et a au moins 3 sommets. S'il y a un point d'articulation, tous les sommets le sont, par sommet-transitivité. Soit alors deux arêtes {e,x} et {e,y} dans deux blocs distincts passant par le sommet associé à e. Alors xy^-1 est d'ordre fini m, ce qui permet de construire un cycle de longueur 2m contenant les deux arêtes. Ce qui contredit l'appartenance à deux blocs distincts.

Dans le cas orienté, le graphe de Cayley de

₄ avec un générateur formé d'une permutation circulaire et d'une transposition qui l'engendrent n'est pas hamiltonien. Voir figure 5.2, et belle preuve dans [78].

Figure 5.2 : Le graphe de Cayley orienté du groupe ₄ avec (1234) et (12)

Les graphe de Cayley de

₄ (le groupe alterné des permutations de 4 éléments a 12 sommets. Il y a 3 graphes de Cayley orientés de degré 2. Certain(s) sont hamiltoniens, d'autre(s) non. Voir figure 5.3.

Figure 5.3 : Graphes de Cayley orienté du groupe ₄ avec 2 générateurs

Cependant, le cycle hamiltonien n'a en général que peu de rapport avec la structure de groupe. Ce qui rend
ennuyeuse
intéressante¹
la recherche de tels circuits ou cycles, voire la décomposition de l'ensemble des arêtes en de tels circuits ou cycles.

Pour en savoir plus, voir [65] ou [122] ou [7] par exemple.

Figure 5.4 : Le graphe de Cayley orienté du groupe de Hamilton à 8 éléments

Le graphe orienté de la figure 5.4 est biparti, hamiltonien. Le groupe est formé des 8 quaternions ±1,± i,± j,± k.

1: biffer la mention inutile