Grafo simétrico

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 Petersen é um grafo (cúbico) simétrico. Qualquer par de vértices ligados pode ser mapeado para outro por um automorfismo, uma vez que qualquer anel de cinco vértices pode ser mapeado para qualquer outro.
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


No campo da matemática da teoria dos grafos, um grafo G é simétrico (ou arco-transitivo) se, dados quaisquer dois pares de vértices ligados u1v1 e u2v2 de G , há um automorfismo

f : V(G) → V(G)

tal que

f(u1) = u2 and f(v1) = v2.1

Em outras palavras, um grafo é simétrico se seu grupo de automorfismo age transitivamente em pares ordenados de vértices ligados (isto é, sobre as arestas consideradas como tendo um sentido).2 Tal grafo é chamado às vezes também 1-arco-transitivo2 ou flag-transitivo.3

Por definição (ignorando u1 e u2), um grafo simétrico sem vértices isolados deve também ser vértice-transitivo.1 Como a definição acima mapeia uma aresta a outra, um grafo simétrico também deve ser aresta-transitivo. Contudo, um grafo aresta-transitivo não precisa ser simétrico, uma vez que ab pode mapear a cd, mas não a dc. Grafos simétricos, por exemplo, aão aresta-transitivos e regulares, mas não vértice-transitivos.

Todo grafo simétrico conexo deve, portanto, ser tanto vértice-transitivo quanto aresta-transitivo, e o inverso é verdadeiro para grafos de grau ímpar.3 No entanto, para graus pares, existem grafos conectados que são vértice-transitivos e aresta-transitivos, mas não simétricos.4 Tais grafos são denominados meio-transitivos.5 O menor grafo conexo meio-transitiva é o grafo de Holt, com grau 4 e 27 vértices.1 6 De forma confusa, alguns autores usam o termo "grafo simétrico" para significar um grafo que é vértice-transitivo e aresta-transitivo, ao invés de um grafo arco-transitivo. Tal definição inclui grafos meio-transitivos, que são excluídos pela definição acima.

Um grafo distância-transitivo é aquele em que em vez de considerar pares de vértices ligados (i.e. vértices a uma distância de um), a definição abrange dois pares de vértices, cada um à mesma distância. Tais grafos são automaticamente simétricos, por definição.1

Um t-arco é definido como uma sequência de t+1 vértices ligados, com quaisquer vértices repetidos estando a mais de 2 passos distante. Um grafo t-transitivo é um grafo tal que o grupo de automorfismo atua transitivamente nos t-arcos, mas não nos (t+1)-arcos. Uma vez que os 1-arcos são simplesmente arestas, qualquer grafo simétrico de grau 3 ou superior tem que ser t-transitivo para algum t, e o valor de t pode ser usado para além disso classificar grafos simétricos. O cubo é 2-transitivo, por exemplo.1

Exemplos[editar | editar código-fonte]

Combinando a condição de simetria com a restrição de que os grafos sejam cúbicos (ou seja, todos os vértices tem grau 3) resulta abolutamente uma forte condição, e tais grafos são raros o bastante para serem citados. O censo de Foster e suas extensões fornecem tais listas.7 O censo de Foster foi iniciado na década de 1930 por Ronald M. Foster enquanto ele era um contratado pela Bell Labs,8 e em 1988 (quando Foster estava com 92 anos de idade1 ) o então censo de Foster corrente (listando todos os grafos cúbicos simétricos até 512 vértices) foi publicado em forma de livro.9


Referências

  1. a b c d e f BIGGS, Norman. Algebraic Graph Theory. 2ª ed. Cambridge: Cambridge University Press, 1993. ISBN 0-521-45897-8
  2. a b GODSIL, Chris; ROYLE, Gordon. Algebraic Graph Theory. New York: Springer, 2001. isbn 0-387-95220-9
  3. a b BABAI, L.; GRAHAM, R. (ed.); GROETSCHEL, M.(ed.); LOVASZ, L.(ed.). Handbook of Combinatorics. [S.l.]: Elsevier, 1996.
  4. BOUWER, Z.. (1970). "Vertex and Edge Transitive, But Not 1-Transitive Graphs". Canad. Math. Bull. 13: 231–237.
  5. GROSS, J.L.; YELLEN, J.. Handbook of Graph Theory. [S.l.]: CRC Press, 2004. p. 491. ISBN 1584880902
  6. HOLT, Derek F.. (1981). "A graph which is edge transitive but not arc transitive". Journal of Graph Theory 5 (2): 201–204. DOI:10.1002/jgt.3190050210..
  7. Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
  8. Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
  9. "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0919611192

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