graphe de Cayley

Imaginez six positions numérotées de 0 à 5 sur un cadran. Depuis chaque position, une flèche « +1 » mène à la suivante, en revenant à 0 après 5. Une flèche « +2 » fait avancer de deux positions.

Ce dessin est un graphe de Cayley. Chaque position représente un élément du groupe, et chaque couleur de flèche représente une opération autorisée. Le même motif part de chaque sommet, car la règle du groupe est partout la même.

Soit un groupe fini, noté G, et un ensemble de ses éléments, noté S. Le graphe de Cayley orienté à droite possède un sommet pour chaque élément de G. Pour tout sommet g et tout élément s de S, il contient un arc étiqueté s allant de g vers le produit g·s. Cette relation s'écrit $h=g\cdot sh=g\backslash cdot\; s$, où h désigne le sommet d'arrivée.

Chaque sommet a donc exactement autant d'arcs sortants qu'il y a d'éléments dans S, en comptant une boucle si l'élément neutre appartient à S. Le graphe est connexe lorsque l'on oublie le sens des arcs si et seulement si S engendre G. Dans le cadre fini de la définition source, cette condition rend aussi tout sommet accessible depuis tout autre en suivant les orientations.

La convention doit toujours être annoncée. On peut multiplier à gauche plutôt qu'à droite, ajouter les inverses des générateurs, ou oublier orientations et étiquettes. Ces choix changent le dessin, mais les parcours répétés associés à un générateur font apparaître ses cycles et ses orbites.

Un graphe de Cayley repose sur quatre données liées. Le groupe fournit les sommets et la loi de composition. L'ensemble générateur fournit les types d'arcs. L'étiquette indique quel générateur transforme le sommet de départ. Enfin, l'orientation enregistre le sens de la multiplication choisie.

La loi du groupe détermine chaque extrémité : depuis l'élément g, l'étiquette du générateur s impose l'arrivée g·s. Le choix de l'ensemble S détermine à la fois le nombre d'arcs sortants et la connexité. Les positions, les longueurs, les croisements et les couleurs du dessin ne définissent pas le graphe ; ils servent seulement à le lire. Le groupe, S et la convention de multiplication suffisent à reconstruire tous les arcs.

Prenons le groupe des entiers modulo 6 pour l'addition. Ses éléments sont 0, 1, 2, 3, 4 et 5, et l'ensemble générateur choisi est {1, 2}. Les résultats sont toujours réduits modulo 6.

1. Plaçons un sommet pour chacun des six éléments.
2. Depuis chaque sommet x, traçons l'arc « +1 » vers x + 1 modulo 6.
3. Depuis le même sommet, traçons l'arc « +2 » vers x + 2 modulo 6.
4. Par exemple, 5 + 1 donne 0 et 5 + 2 donne 1 modulo 6.

Le graphe obtenu a exactement 6 sommets et 12 arcs orientés, soit 2 arcs sortants par sommet. Les arcs « +1 » forment un cycle passant par les six sommets. Les arcs « +2 » forment deux cycles, 0–2–4–0 et 1–3–5–1.

Pour contrôler la construction, on vérifie sur chaque sommet la présence d'une sortie de chaque type. Le générateur 1 permet à lui seul d'atteindre les six sommets : le graphe est donc connexe.

En théorie des groupes, on suit les arcs pour comparer des suites de générateurs et repérer les cycles qu'elles produisent. Une table de multiplication convient mieux lorsque l'on veut lire directement tous les produits possibles.

En théorie de la complexité, le graphe transforme l'enchaînement d'opérations en chemins. On peut alors étudier le nombre minimal d'étapes entre deux éléments ; une simple liste d'éléments ne conserve pas cette information de parcours.

En cryptographie, cette représentation sert lorsque les transformations considérées forment un groupe et que leurs enchaînements comptent. Si l'enjeu est seulement de calculer un produit isolé, l'écriture algébrique reste plus directe.

Un graphe de Cayley ne se confond pas avec une table de Cayley. Le graphe montre les multiplications par les seuls générateurs choisis sous forme de parcours ; la table donne le produit de chaque paire d'éléments. Pour le groupe modulo 6 avec {1, 2}, le graphe a deux sorties par sommet, tandis que la table comporte les 36 produits ordonnés.

Un graphe régulier quelconque n'est pas automatiquement un graphe de Cayley. Dans un graphe de Cayley, les sommets correspondent aux éléments d'un même groupe et chaque étiquette agit partout par la même multiplication. La seule égalité des degrés ne fournit pas cette structure.

La régularité ne garantit pas la connexité. Dans le groupe modulo 6, l'ensemble {2} donne bien une sortie par sommet, mais sépare les cycles 0–2–4–0 et 1–3–5–1. Il faut vérifier que l'ensemble choisi engendre tout le groupe.

Le sens des arcs dépend d'une convention. La multiplication à droite relie g à g·s, tandis que la multiplication à gauche relie g à s·g. Pour un groupe non commutatif, ces deux calculs ne doivent pas être mélangés.

L'identité dans l'ensemble générateur crée une boucle à chaque sommet. Si un générateur et son inverse appartiennent à S, deux arcs de sens opposés relient certaines paires de sommets. Un dessin non orienté peut les fusionner en une seule arête. Il faut donc annoncer si le dessin est orienté, étiqueté ou simplifié.

La définition source se place dans un groupe fini. La même construction s'étend aux groupes infinis, mais le graphe possède alors une infinité de sommets et ne peut pas être représenté en entier.

L'article Les débuts des groupes replace la notion de groupe dans son histoire et éclaire le cadre algébrique que le graphe rend visible.