Grafo di Cayley

Sia ${\displaystyle G}$ un gruppo e ${\displaystyle S}$ un insieme di generatori per ${\displaystyle G}$ . Il grafo di Cayley di ${\displaystyle G}$ è un grafo costruito a partire da ${\displaystyle G}$ e ${\displaystyle S}$ nel modo seguente.^[1]

• I vertici del grafo sono gli elementi di ${\displaystyle G}$ ,
• gli spigoli del grafo sono le coppie ${\displaystyle (g,gs)}$ al variare di ${\displaystyle g}$ in ${\displaystyle G}$ e ${\displaystyle s}$ in ${\displaystyle S}$ .

Si può decidere di dare un colore diverso ad ogni generatore ${\displaystyle s\in S}$ ed assegnare quel colore allo spigolo ${\displaystyle (g,gs)}$ . Si può anche dare un'orientazione allo spigolo, che parte da ${\displaystyle g}$ ed arriva in ${\displaystyle gs}$ .

Gruppi abeliani

Sia ${\displaystyle G=\mathbb {Z} }$ il gruppo degli interi e ${\displaystyle S=\{1\}}$ consista del generatore standard 1. Il grafo di Cayley è l'insieme di vertici ${\displaystyle \mathbb {Z} }$ , con un segmento per ogni coppia ${\displaystyle (n,n+1)}$ . Topologicamente il grafo di Cayley è quindi una retta.

Sia ${\displaystyle G=\mathbb {Z} _{n}}$ il gruppo ciclico di ordine ${\displaystyle n}$ e ${\displaystyle S=\{1\}}$ il generatore standard. Il grafo di Cayley è l'insieme di vertici ${\displaystyle 0,1,\ldots ,n-1}$ , con un segmento per ogni coppia ${\displaystyle (i,i+1)}$ , inclusa la coppia ${\displaystyle (n-1,0)}$ . Il grafo di Cayley è quindi un poligono con ${\displaystyle n}$ lati.

Prodotto diretto

Il grafo di Cayley del prodotto di gruppi è il prodotto cartesiano dei grafi di Cayley di ogni fattore, purché l'insieme dei generatori per il prodotto sia scelto in modo naturale sulla base dei generatori dei singoli fattori^[2].

Il grafo di Caley di ${\displaystyle \mathbb {Z} ^{2}}$ con generatori ${\displaystyle (1,0)}$ e ${\displaystyle (0,1)}$ è una griglia nel piano ${\displaystyle \mathbb {R} ^{2}}$ .

Gruppo diedrale

Il grafo di Cayley del gruppo diedrale ${\displaystyle D_{4}}$ presentato nel modo seguente

${\displaystyle \langle a,b\ |\ a^{4}=b^{2}=e,bab=a^{3}\rangle }$

con generatori ${\displaystyle a}$ e ${\displaystyle b}$ è mostrato nella figura a sinistra. Nella figura di destra è mostrato il grafo di Cayley dello stesso gruppo ${\displaystyle D_{4}}$ rispetto ad un altro insieme di generatori.

Gruppo libero

Il grafo di Cayley del gruppo libero con due generatori ${\displaystyle a}$ e ${\displaystyle b}$ è mostrato più in alto: si tratta di un albero infinito in cui ogni vertice è adiacente a quattro spigoli.

• Generatori di un gruppo
• Gruppo libero

• Wikimedia Commons contiene immagini o altri file su grafo di Cayley

• (EN) Eric W. Weisstein, Grafo di Cayley, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica