Du chemin hamiltonien au polygone (et aux étoiles {n/k})

Même objet, deux costumes : théorie des graphes 🎛️ et géométrie sur un cercle 🧭. Les croisements sont autorisés (polygones étoilés / auto-intersectants).

📈 Valeurs (exemples)

a(3)=1 a(4)=2 a(5)=4 a(6)=12 a(7)=39 a(8)=202 a(9)=1219

rotation ↺ identifiée sens ↔ identifié croisements OK ✴️

🧩 1) Définition “graphes” (Kₙ)

Graphe complet Kₙ : chaque sommet est relié à tous les autres.

Cycle hamiltonien : C = (v0, v1, …, v(n-1)) avec {vi} = {0…n-1} + fermeture (v(n-1) → v0) Identifications (même forme) : • rotation du point de départ • inversion du sens

🔁 Cycle visite tous les sommets 1× et revient au départ

↺ Rotation le choix de v0 ne change pas la forme

↔ Inversion parcours horaire/anti-horaire identifiés

🧭 2) Définition “géométrie” (cercle)

On place n points équidistants sur un cercle, puis on relie selon l’ordre du cycle.

Points : pi = (cos(2πi/n), sin(2πi/n)) Polygone associé : Γ(C) = segments [p(v_i), p(v_{i+1})] avec v_n = v_0 ➡️ Croisements autorisés

🟦 convexes ✴️ étoilés 🧵 auto-intersectants

🪄 3) Passage “cycle → polygone”

🧾 Donnée

un cycle C = (v0,…,v(n−1))

🧭 Placement

p0…p(n−1) sur un cercle (équidistants)

🧵 Tracé

relier p(v_i) → p(v_{i+1}), fermer

Même forme ⇔ mêmes arêtes “cylindrées” : C ~ rotation(C) ~ reverse(C) Intuition : un cycle = un ordre de visite un polygone = cet ordre dessiné

🌟 4) Les étoiles régulières {n/k}

{n/k} = “pas constant” : on avance de k sommets modulo n.

Cycle de pas k : C(n,k) = (0, k, 2k, 3k, …) mod n Condition étoile “pure” : gcd(n,k) = 1 ✅ (cycle hamiltonien) Symétrie : {n/k} = {n/(n−k)} (même dessin, sens inverse)

ex: {5/1} pentagone ex: {5/2} étoile ex: {7/2}, {7/3}