Sur un graphe planaire, on nomme “Cycle hamiltonien” une boucle fermée qui passe une fois et une seule par chaque sommet du graphe : en effet, c’est le mathématicien Hamilton qui étudia au 19e le problème de l’existence, dans un graphe donné, d’un cycle hamiltonien.
Un graphe qui admet un cycle hamiltonien est dit "graphe hamiltonien".
Quand un graphe est de petite taille, on a assez vite une idée de la possibilité d’y trouver un cycle hamiltonien. Mais quand le graphe est grand, c’est une autre histoire dont on sait maintenant qu’elle est “intrinsèquement difficile”.
Exemple
En projetant un dodécaèdre régulier sur un plan, on peut ainsi construire un graphe planaire (c’est à dire dont les arêtes ne se coupent pas) dont les sommets et les arêtes sont les projetés de ceux du solide. Une des faces du polyèdre devient la face externe du graphe. Représenter ce graphe ; est-ce un graphe hamiltonien ?
La relation de Grinberg
Un mathématicien russe du nom de Grinberg a découvert une relation qui est vérifiée par tous les graphes qui possèdent un cycle hamiltonien. Cette relation n’est d’aucune aide s’il s’agit de prouver qu’un graphe possède un cycle hamiltonien, mais elle peut aider à prouver que ce n’est pas le cas…
Nous allons la démontrer.
Données : G est un graphe “planaire” possédant un cycle hamiltonien. Soit a le nombre d’arcs du cycle, et r le nombre d’arcs de G situés à l’intérieur du cycle. Notons In le nombre de régions intérieures au cycle et possédant n côtés, et En le nombre de régions extérieures au cycle et possédant n côtés.
1) Prouver que, si k est le plus grand des nombres de côtés des régions intérieures au cycle, alors : I1 + I2 + I3 + … Ik = r + 1.
2) Démontrer que : I1 + 2I2 + 3I3 + … kIk = 2r + a.
3) En déduire que : –I1 + I3 + 2I4 + 3I5 + … (k–2)Ik = a – 2.
4) Prouver que, si l est le plus grand des nombres de côtés des régions extérieures au cycle, alors : –E1 + E3 + 2E4 + 3E5 + … (l–2)El = a – 2.
5) En déduire que, si m est le plus grand des nombres l et k, alors :
C’est la “relation de Grinberg” !
Applications
1) Vérifier cette relation sur quelques graphes de votre choix.
2 Démontrer que le graphe de la figure de gauche n’a pas de cycle hamiltonien.
3) Et celui de la figure de droite ?
4) Sauriez-vous trouver un graphe non hamiltonien vérifiant la relation de Grinberg ?
![\[(E_1-I_1)+(I_3-E_3)+2(I_4-E_4)+3(I_5-E_5)+\cdots+(m-2)(I_m-E_m)=0\]](grham001.gif)
