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 Ter ES         

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é :


Vous pouvez tourner/réduire/agrandir en déplaçant l'un des deux pentagones réguliers du graphe, mais au risque
d'obtenir un graphe non planaire !

b/ Une solution :

On part de A en direction de E. Suivre ensuite les arcs orientés.

 


© Serge Mehl - www.chronomath.com