Grafo de Cayley

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
O grafo de Cayley do grupo livre em dois geradores a e b
Famílias de grafos definidos por seus automorfismos
distância-transitivo \rightarrow distância-regular \leftarrow fortemente regular
\downarrow
simétrico (arco-transitivo) \leftarrow t-transitivo, t ≥ 2 .
\downarrow
(se conectado)
transitivo nos vértices e nas arestas \rightarrow aresta-transitivo e regular \rightarrow aresta-transitivo
\downarrow \downarrow
vértice-transitivo \rightarrow regular
\uparrow
grafo de Cayley anti-simé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.

Definição[editar | editar código-fonte]

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

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

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

Exemplos[editar | editar código-fonte]

  • Suponha que 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 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 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 \mathbb{Z}^2 com o conjunto de geradores que consiste em quatro elementos (\pm 1,0),(0,\pm 1) é a grade no plano \mathbb{R}^2, enquanto que para o produto direto \mathbb{Z}_n \times \mathbb{Z}_m com geradores semelhantes o grafo de Cayley é a grade finita n\times m 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
 \langle \alpha, \beta | \alpha^4 = \beta^2 = e, \alpha \beta = \beta \alpha^3 \rangle. \,


Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]

Referências

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