Graphe de Cayley
Un article de Wikipédia, l'encyclopédie libre.
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.
Étant donné un groupe G et un ensemble générateur de ce groupe S, le graphe de Cayley est construit comme suit:
- À chaque élément gi de G, on associe un sommmet vi
- À chaque élément si de S, on associe une couleur ci
- Il y a une arête dirigée de couleur ci de v1 vers v2 si g2 = g1 * si
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 de g à sg).
[modifier] 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 n éléments, chaque sommet a n arêtes entrantes, et n arêtes sortantes.
- Les cycles du graphes correspondent aux relations vérifiées par les générateurs.
- Si s et s − 1 sont tous les deux dans l'ensemble de générateurs, on remplace souvent chaque paire d'arêtes orientées correspondant à s et s − 1 par une seule arête non orientée.
[modifier] Exemples
Le graphe de Cayley du groupe libre à deux générateurs est représenté en haut à droite de la page. (e est l'élément neutre). Un pas vers la droite correspond à une multiplication par a, vers la gauche par a − 1, vers le haut par b et b − 1 vers le bas. Comme il n'y a pas de relations dans le groupe libre (par définition), son graphe de Cayley est acyclique.
