Grafo di Cayley

In matematica, il grafo di Cayley è un grafo associato ad un gruppo, che traduce alcune proprietà algebriche del gruppo in proprietà metriche del grafo. Il grafo di Cayley è uno strumento centrale in topologia e nella teoria geometrica dei gruppi.

Definizione

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.

• 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}$.

Esempi

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.

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.

Note

Voci correlate

• Generatori di un gruppo
• Gruppo libero

Altri progetti

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

Collegamenti esterni

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