Graphe de Cayley
![Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/Info_Simple.svg/12px-Info_Simple.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a1/2017-fr.wp-orange-source.svg/45px-2017-fr.wp-orange-source.svg.png)
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Cayley_graph_of_F2.svg/220px-Cayley_graph_of_F2.svg.png)
En mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes.
Définition
Familles de graphes définies par leurs automorphismes | ||||
---|---|---|---|---|
distance-transitif | → | distance-régulier | ← | fortement régulier |
↓ | ||||
symétrique (arc-transitif) | ← | t-transitif, (t ≥ 2) | symétrique gauche (en) | |
↓ | ||||
(si connexe) sommet-transitif et arête-transitif | → | régulier et arête-transitif | → | arête-transitif |
↓ | ↓ | ↓ | ||
sommet-transitif | → | régulier | → | (si biparti) birégulier |
↑ | ||||
graphe de Cayley | ← | zéro-symétrique | asymétrique |
Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit :
- À chaque élément de , on associe un sommet .
- À chaque élément de , on associe une couleur .
- Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .
On peut aussi associer à chaque générateur une direction plutôt qu'une couleur, mais il est alors parfois impossible de représenter le graphe dans le plan. Dans certains contextes, on utilise la multiplication à gauche plutôt qu'à droite (les arêtes vont alors de à ).
Propriétés
- Comme l'ensemble générateur d'un groupe n'est pas unique, la structure des graphes de Cayley d'un groupe donné n'est pas unique.
- Si l'ensemble générateur a éléments, chaque sommet a arêtes entrantes, et arêtes sortantes.
- Les cycles du graphe correspondent aux relations vérifiées par les générateurs.
- Si et sont tous les deux dans l'ensemble de générateurs, on remplace souvent chaque paire d'arêtes orientées correspondant à et par une seule arête non orientée.
Exemples
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/GrapheCayley-C3xC3semiC2-Tore.svg/220px-GrapheCayley-C3xC3semiC2-Tore.svg.png)
Le graphe de Cayley du groupe libre à deux générateurs est représenté en haut à droite de la page. ( est l'élément neutre). Un pas vers la droite correspond à une multiplication par , vers la gauche par , vers le haut par et vers le bas. Comme il n'y a pas de relations dans le groupe libre (par définition), son graphe de Cayley est acyclique.
À droite se trouve un dessin du graphe de Cayley d'un groupe d'ordre 18 avec présentation . Il est engendré par trois éléments d'ordre 2, qui sont donc représentés par des arêtes non-orientées de trois couleurs différentes; chaque sommet est lié à une arête de chaque couleur. En suivant les arêtes on peut vérifier que les autres relations sont satisfaites. Si par exemple pour les générateurs x, y, et z on choisit respectivement les couleurs rouge, vert, et bleu (mais peu importe, la présentation est parfaitement symétrique), on voit que, partant d'un sommet quelconque, la suite rouge-vert-rouge-vert-rouge-vert nous remet à notre point de départ (alors (xy)3 = 1), et aussi la suite rouge-vert-bleu-rouge-vert-bleu (alors (xyz)2 = 1).
Voir aussi
Article connexe
Lien externe
(en) Eric W. Weisstein, « Cayley Graph », sur MathWorld
Bibliographie
- (en) Arthur Cayley, « On the theory of groups », Proc. London Math. Soc., no 9, , p. 126-133
- (en) H. S. M. Coxeter et W. O. J. Moser (de), Generators and Relations for Discrete Groups, Springer, (réimpr. 2013), 3e éd. (1re éd. 1957), 164 p. (ISBN 978-3-662-21946-1, présentation en ligne), « 3. Graphs, Maps and Cayley Diagrams », p. 18-32.
Portail des mathématiques
Portail de l'informatique théorique