Codage-décodage de cycles hamiltoniens d'un polyèdre régulier

Codage-décodage de cycles hamiltoniens d'un polyèdre régulier

Toute cette page comporte peut-être des erreurs fondamentales dans les méthodes exposées, merci de bien vouloir me les signaler à :   aesculier   "arobase"   infonie.fr

I. But du codage d'un cycle hamiltonien d'un polyèdre

Considérant un polyèdre régulier à n sommets et l'ensemble des cycles hamiltoniens partant d'une arête tracés sur ce polyèdre, l'idée est d'associer à un cycle une suite de n codes définissant complétement sa forme géométrique indépendante de sa position sur le polyèdre donc de reconstruire un cycle égal à un déplacement près.
Ayant un cycle, deux résultats à établir :

     1. Trouver une façon de coder un sommet.
     2. les différents codes selon l'arête de départ pour parcourir le cycle.
     3. la relation entre les codes d'un cycle et de ses transformés par isométrie.

Le but final étant de trouver les formes élémentaires, à une isométrie près, des cycles d'un polyèdre régulier.
Par exemple, appliquer cela à l'icosaèdre qui a 512 de cycles partant d'une arête.

II. Principe du codage d'un cycle hamiltonien d'un polyèdre

Considérons un cycle (S) sur polyèdre de centre O(0,0,0) et trois sommets consécutifs (A,B,C) sur le parcours de ce cycle.
Au sommet B arrivent p arêtes autres que l'arête AB ; l'arête BC a donc p positions possibles.
Je vais associer un code à chacune soit (a1,a2,..ap), code qui soit indépendant de la position des points (A,B,C).
Le point C sera donc parfaitement déterminé à partir des points (A,B) et du code ai attribué à C.

Définition du code attribué à un sommet

Soit M le milieu du segment AB, considérons le repère orthonormé direct () avec I1 porté par , J1 porté AB et complété par K1 perpendiculaire au plan OAB.
Les p positions possibles de C sont codées par (a1,a2,..ap) ; les composantes associées dans ce repère (I1,J1,K1)sont indépendantes du point B.
Le point C, de code ai, sera obtenu par + ai[1]*+ ai[2]*+ ai[3]*.
Partant de l'arête de départ [A,B], on peut ainsi de proche en proche définir le codage des sommets du cycle en terminant par le codage des deux points de l'arête de départ.
Le code ainsi obtenu définit localement les sommets du cycle les uns par rapport aux autres donc caractérise la forme géométrique d'un cycle indépendamment de sa position.
exemple : [a2,a3,a1,a2,a1,a4,a2,a4,a2,a1,a4,a4], codage d'un cycle de l'icosaèdre.

Décodage : construction d'un cycle à partir de son code
Ayant le code d'un cycle, on peut construire un cycle de même forme géométrique sur le polyèdre.
Partant d'une arête [A,B], du repère (I1,J1,K1) associé, on peut construire le 3-ième sommet du cycle, puis de proche en proche tous les autres sommets.

Propriétés du codage

Les exemples de codes et images suivants sont ceux d'un icosaèdre.

codes par permutations circulaires du code d'un cycle
[ a2,a3,a1,a2,a1,a4,a2,a4,a2,a1,a4,a4] le code d'un cycle de l'icosaèdre
[a4,a2,a1,a4,a4 ,a2,a3,a1,a2,a1,a4,a2] un code par permutation circulaire
On obtient deux cycles de même forme géométriques.
Cela revient à coder le cycle en partant d'un autre sommet.

On peut faire de même en sens inverse
Une forme géométrique de cycle a donc la même classe de codes obtenus par permutations circulaires ( dans les deux sens ) d'un code de ce cycle.

code obtenu codant le symétrique-plan ou symétrique-centrale d'un cycle
Dans le cas de l'icosaèdre, cela revient à permuter les indices (1,2) et(3,4) du code du cycle.( à adapter pour les autres polyèdres)
La forme géométrique symétrique de celle d'un cycle a donc pour classe de codes la classe des permutations circulaires( dans les deux sens ) du code du symétrique du cycle par rapport au centre du polyèdre.
  [a2,a3,a1,a4,a2,a3,a4,a1,a3,a2,a4,a1] code du cycle
  [a1,a4,a2,a3,a1,a4,a3,a2,a4,a1,a3,a2] code du cycle symétrique
Les deux cycles symétriques par rapport à un plan.

III. Application : nombre de cycles d'un polyèdre différents à une isométrie près
Explications dans le cas de l'icosaèdre.
On peut se limiter aux cycles partant d'une arête.
Soit Lcycles la liste des 512 cycles ainsi obtenue , Lcodes la liste des codes associés à chacun.

La procédure codePerm donne l'ensemble des permutations circulaires ( dans les deux sens ) du code d'un cycle.

On va établir les cycles différents à une isométrie près pour les cycles :
[Lcycles[1],Lcycles[2],..,Lcycles[i]] pour i variant de 1 à 512.

On suppose le programme réalisé jusqu'à l'ordre i-1 et obtenus :
    1. la liste LcyclesDif des cycles différents à une isométrie près
    2. La liste LcodesDif des codes de la liste LcyclesDif
    3. Un ensemble associé de codes appelé LcodesAssocies

A l'ordre i, soient :
  u1=Lcodes[i]
  u2 le code du symétrique par rapport au plan xOy du cycle Lcycles[i]
  ens1=codePerm(u1) ; ens2=codePerm(u2)

Si les intersections (ens1,LcodesAssocies),(ens2,LcodesAssocies) sont vides
  on ajoute :
     Lcycles[i] à liste LcyclesDif
     u1 à LcodesDif
     les ensembles (ens1, ens2) à LcodesAssocies
sinon
   on passe à l'ordre suivant

Le programme Maple réalisant cela trouve 17 cycles( et codes) élémentaires non isométriques.
Ce programme est téléchargeable : ICI

VI. Illustrations :tétraèdre, cube, octaèdre et dodécaèdre
Images des cycles hamiltoniens partant d'une arête ; avec fond couleur cyan, la/les formes géométriques à une isométrie près.

le tétraèdre

le cube

l'octaèdre

le dodécaèdre

codes par permutations circulaires du code d'un cycle [ a2,a3,a1,a2,a1,a4,a2,a4,a2,a1,a4,a4] le code d'un cycle de l'icosaèdre [a4,a2,a1,a4,a4 ,a2,a3,a1,a2,a1,a4,a2] un code par permutation circulaire On obtient deux cycles de même forme géométriques. Cela revient à coder le cycle en partant d'un autre sommet.
On peut faire de même en sens inverse Une forme géométrique de cycle a donc la même classe de codes obtenus par permutations circulaires ( dans les deux sens ) d'un code de ce cycle.
code obtenu codant le symétrique-plan ou symétrique-centrale d'un cycle Dans le cas de l'icosaèdre, cela revient à permuter les indices (1,2) et(3,4) du code du cycle.( à adapter pour les autres polyèdres) La forme géométrique symétrique de celle d'un cycle a donc pour classe de codes la classe des permutations circulaires( dans les deux sens ) du code du symétrique du cycle par rapport au centre du polyèdre. [a2,a3,a1,a4,a2,a3,a4,a1,a3,a2,a4,a1] code du cycle [a1,a4,a2,a3,a1,a4,a3,a2,a4,a1,a3,a2] code du cycle symétrique Les deux cycles symétriques par rapport à un plan.