ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

 Chemin hamiltonien sur un polyèdre          niveau TerES

En 1859, Hamilton propose un jeu de cheminement sur un dodécaèdre régulier consistant, à partir d'un sommet quelconque de passer une fois et une seule par tous les sommets et de revenir au sommet initial en cheminant sur les arêtes du polyèdre : en théorie des graphes, on parle aujourd'hui de cycle hamiltonien.

a/ Construire un graphe planaire équivalent à ce polyèdre : on doit respecter le nombre de sommets (au nombre de 20) et les arêtes qui les relient. Deux arêtes du graphe obtenu ne peuvent s'intersecter en dehors d'un sommet.

b/ Proposer une solution.

Si vous séchez après avoir bien cherché :


© Serge Mehl - www.chronomath.com

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Indications :

a/ Construction du graphe :    

Nommons ABCD le pentagone rose vu de face et de front, et EFGH le pentagone "du fond" représenté en pointillés :

Depuis A, B, C, D et E partent 5 arêtes d'extrémités respectives K, M, O, Q et S :

Vous avez dû constater que la représentation de ces arêtes extérieurement à ABCDE entraînera le croisement d'arêtes reliant le pentagone FGHIJ. le graphe ne sera pas planaire;

Afin de contourner ce problème, "retournons" les arêtes issues de A, B, C, D et E vers l'intérieur du pentagone. Puis tout se passe comme si le polyèdre était écrasé sur la face ABCD mais en respectant un peu de symétrie... Voici une représentation où ABCDE a été fortement agrandie pour plus de lisibilité :

Voici la même figure générée au moyen du logiciel de géométrie dynamique Cabri Géomètre, dans sa version CabriJava pour Internet :


Si votre navigateur accepte les applets Java :
Vous pouvez tourner/réduire/agrandir en déplaçant l'un des deux pentagones réguliers ABCDE
et FGHIJ mais au risque d'obtenir un graphe non planaire !

Figure CabriJava.class : Utiliser Microsoft Internet Explorer en activant Java

b/ Une solution :    

On part de A en direction de E et on suit les arcs orientés :

Voici la même figure générée au moyen du logiciel de géométrie dynamique Cabri Géomètre, dans sa version CabriJava pour Internet :

 
Si votre navigateur accepte les applets Java :
Vous pouvez tourner/réduire/agrandir en déplaçant les sommets des pentagones réguliers du graphe,
à savoir ABCDE, FGHIJ et KMOQS, ce dernier peut devenir étoilé.
Figure CabriJava.class : Utiliser Microsoft Internet Explorer en activant Java


© Serge Mehl - www.chronomath.com