Grafo di Cayley

Da Wikipedia, l'enciclopedia libera.
Il grafo di Cayley del gruppo libero su due generatori a e b è un albero infinito in cui ogni vertice è adiacente a quattro spigoli.

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[modifica | modifica sorgente]

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

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

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

Esempi[modifica | modifica sorgente]

Gruppi abeliani[modifica | modifica sorgente]

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

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

Prodotto diretto[modifica | modifica sorgente]

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 \mathbb Z^2 con generatori (1,0) e (0,1) è una griglia nel piano \mathbb R^2.

Gruppo diedrale[modifica | modifica sorgente]

Grafo di Cayley del gruppo diedrale D_4 con generatori a e b
Grafo di Cayley di D_4 con generatori b e c

Il grafo di Cayley del gruppo diedrale D_4 presentato nel modo seguente

\langle a,b\ |\ a^4 = b^2 = e, bab = a^3 \rangle

con generatori a e b è mostrato nella figura a sinistra. Nella figura di destra è mostrato il grafo di Cayley dello stesso gruppo D_4 rispetto ad un altro insieme di generatori.

Gruppo libero[modifica | modifica sorgente]

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

Note[modifica | modifica sorgente]

  1. ^ Arthur Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation in Amer. J. Math., vol. 2, nº 1, 1878, pp. 174–176, JSTOR 2369306.
  2. ^ Nel prodotto di due gruppi $G_1\times G_2$ si prendono come generatori gli elementi $(s_1,0)$ e $(0,s_2)$ al variare di $s_1$ e $s_2$ fra i generatori di $G_1$ e $G_2$.

Voci correlate[modifica | modifica sorgente]

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