Grafo de Cayley

Em matemática, área da teoria dos grafos, um grafo de Cayley, também conhecido como grafo colorido de Cayley, diagrama de Cayley, diagrama de grupo, ou grupo colorido^[1] é um grafo que codifica a estrutura abstrata de um grupo. Sua definição é sugerida pelo teorema de Cayley (nomeado em honra a Arthur Cayley) e usa um conjunto de geradores específico, usualmente finito, para o grupo. É um instrumento central em combinatória e teoria geométrica de grupos.

O grafo de Cayley do grupo livre em dois geradores a e b

Famílias de grafos definidos por seus automorfismos
distância-transitivo	${\displaystyle \rightarrow }$	distância-regular	${\displaystyle \leftarrow }$	fortemente regular
${\displaystyle \downarrow }$
simétrico (arco-transitivo)	${\displaystyle \leftarrow }$	t-transitivo, t ≥ 2		.
${\displaystyle \downarrow }$ (se conectado)
transitivo nos vértices e nas arestas	${\displaystyle \rightarrow }$	aresta-transitivo e regular	${\displaystyle \rightarrow }$	aresta-transitivo
${\displaystyle \downarrow }$		${\displaystyle \downarrow }$
vértice-transitivo	${\displaystyle \rightarrow }$	regular
${\displaystyle \uparrow }$
grafo de Cayley		antissimétrico		assimétrico

Definição

Suponha que ${\displaystyle G}$ seja um grupo e ${\displaystyle S}$ seja um conjunto de geradores. O grafo de Cayley ${\displaystyle \Gamma =\Gamma (G,S)}$ é um grafo direcionado colorido construído como se segue^[2]

• A cada elemento ${\displaystyle g}$ de ${\displaystyle G}$ é atribuído um vértice: o conjunto de vértices ${\displaystyle V(\Gamma )}$ de ${\displaystyle \Gamma }$ é identificado com ${\displaystyle G.}$
• A cada gerador ${\displaystyle s}$ de ${\displaystyle S}$ é atribuída uma cor ${\displaystyle c_{s}.}$
• Para qualquer ${\displaystyle g\in G,s\in S,}$ os vértices correspondentes aos elementos ${\displaystyle g}$ e ${\displaystyle gs}$ são unidos por uma aresta de cor ${\displaystyle c_{s}.}$ Assim, o conjunto de arestas ${\displaystyle E(\Gamma )}$ consiste em pares da forma ${\displaystyle (g,gs),}$ com ${\displaystyle s\in S}$ proporcionando a cor.

Na teoria geométrica de grupos, o conjunto ${\displaystyle S}$ é geralmente assumido ser finito, simétrico, isto é ${\displaystyle S=S^{-1},}$ e não contendo o elemento identidade do grupo. Neste caso, o grafo de Cayley incolor é um grafo comum: suas arestas não são orientadas e não contém laços se e somente se ${\displaystyle 1\notin S.}$

Exemplos

• Suponha que ${\displaystyle G=\mathbb {Z} }$ é o grupo cíclico infinito e o conjunto S consiste em um gerador padrão e sua inversa (-1 na notação aditiva), então o grafo de Cayley é uma cadeia infinita.

• Similarmente, se ${\displaystyle G=\mathbb {Z} _{n}}$ é o grupo cíclico finito de ordem n e o conjunto S consiste de dois elementos, o gerador padrão de G e o seu inverso, então o grafo de Cayley é o ciclo ${\displaystyle C_{n}.}$

• O grafo de Cayley do produto direto de grupos é o produto cartesiano dos grafos de Cayley correspondentes. Assim, o grafo de Cayley do grupo abeliano ${\displaystyle \mathbb {Z} ^{2}}$ com o conjunto de geradores que consiste em quatro elementos ${\displaystyle (\pm 1,0),(0,\pm 1)}$ é a grade no plano ${\displaystyle \mathbb {R} ^{2},}$ enquanto que para o produto direto ${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$ com geradores semelhantes o grafo de Cayley é a grade finita ${\displaystyle n\times m}$ em um toro.

O grafo de Cayley do grupo diedro D₄ em dois geradores α e β

• O grafo Cayley do grupo diedro D₄ em dois geradores α e β é descrito à esquerda. As setas vermelhas representam a multiplicação à esquerda pelo elemento α. Uma vez que o elemento β é auto-inversível, as linhas azuis que representam a multiplicação à esquerda pelo elemento β são não direcionadas. Portanto, o grafo é misto: ele tem oito vértices, oito setas, e quatro arestas. A tabela Cayley do grupo D₄ pode ser derivada a partir da apresentação do grupo

$${\displaystyle \langle \alpha ,\beta |\alpha ^{4}=\beta ^{2}=e,\alpha \beta =\beta \alpha ^{3}\rangle .}$$

Ver também

• Grafo vértice-transitivo
• Conjunto gerador de um grupo

Ligações externas

• Diagramas Cayley

Referências

1. Wilhelm Magnus, Abraham Karrass, Donald Solitar (1976). Combinatorial Group Theory. [S.l.]: Dover Publications, Inc !CS1 manut: Nomes múltiplos: lista de autores (link)
2. CAYLEY, Arthur (1878). «Desiderata and suggestions: No. 2. The Theory of groups: graphical representation». Amer. J. Math. 1 (2). pp. 174–176