Graphe de Cayley

Graphe de Cayley
Le graphe de Cayley du groupe libre à deux générateurs, a et b

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 une partie génératrice S de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit :

  • À chaque élément gi de G, on associe un sommet 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).

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 graphe 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.

Exemples

GrapheCayley-C3xC3semiC2-Tore.svg

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.

À droite se trouve un dessin du graphe de Cayley d'un groupe d'ordre 18 avec présentation < x,y,z | x2 = y2 = z2 = (xy)3 = (xz)3 = (yz)3 = (xyz)2 = 1 > . 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érents; chaque sommet a 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).


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Cayley de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Graphe De Cayley — Le graphe de Cayley du groupe libre à deux générateurs, a et b 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… …   Wikipédia en Français

  • Graphe de cayley — Le graphe de Cayley du groupe libre à deux générateurs, a et b 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… …   Wikipédia en Français

  • Graphe de Hamming — H(4,2) Notation H(d,q) Nombre de sommets qd Nombre d arêtes …   Wikipédia en Français

  • Graphe tesseract — Une représentation du graphe tesseract. Nombre de sommets 16 Nombre d arêtes 32 Distribution des degrés 4 régulier Rayon 4 …   Wikipédia en Français

  • Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Graphe de Hoffman-Singleton — Schéma du graphe de Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés …   Wikipédia en Français

  • Graphe de Petersen — Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier …   Wikipédia en Français

  • Graphe Petersen — Graphe de Petersen Graphe de Petersen Schéma classique du graphe de Petersen, sous la forme d un pentagone et d un pentagramme concentriques, reliés par cinq rayons. Nombre de sommets 10 Nombre d arêtes 15 Distribution des degrés 3 régulier… …   Wikipédia en Français

  • Graphe de Heawood — Représentation du graphe de Heawood. Nombre de sommets 14 Nombre d arêtes 21 Distribution des degrés 3 régulier Rayon 3 …   Wikipédia en Français

  • Graphe de Sylvester — Nombre de sommets 36 Nombre d arêtes 90 Distribution des degrés 5 régulier Rayon 3 Diamètre 3 Maille 5 Automorphismes 1 440 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”