Saltar para o conteúdo

Grafo de Cayley

Origem: Wikipédia, a enciclopédia livre.
O grafo de Cayley do grupo livre em dois geradores a e b
Famílias de grafos definidos por seus automorfismos
distância-transitivodistância-regularfortemente regular
simétrico (arco-transitivo)t-transitivo, t ≥ 2.

(se conectado)
transitivo nos vértices e nas arestasaresta-transitivo e regulararesta-transitivo
vértice-transitivoregular
grafo de Cayleyantissimétricoassimé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 seja um grupo e seja um conjunto de geradores. O grafo de Cayley é um grafo direcionado colorido construído como se segue[2]

  • A cada elemento de é atribuído um vértice: o conjunto de vértices de é identificado com
  • A cada gerador de é atribuída uma cor
  • Para qualquer os vértices correspondentes aos elementos e são unidos por uma aresta de cor Assim, o conjunto de arestas consiste em pares da forma com proporcionando a cor.

Na teoria geométrica de grupos, o conjunto é geralmente assumido ser finito, simétrico, isto é 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

  • Suponha que é 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 é 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
  • 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 com o conjunto de geradores que consiste em quatro elementos é a grade no plano enquanto que para o produto direto com geradores semelhantes o grafo de Cayley é a grade finita em um toro.
O grafo de Cayley do grupo diedro D4 em dois geradores α e β
  • O grafo Cayley do grupo diedro D4 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 D4 pode ser derivada a partir da apresentação do grupo

Ligações externas

[editar | editar código-fonte]

Referências

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