Grafo de Cayley

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (notícias • livros • acadêmico)). (Setembro de 2021)

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

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.

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

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

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

• Diagramas Cayley