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é : ››››
| 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
(»
extension CheerpJ
) :
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 !
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
(»
extension CheerpJ) :
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é.