Saltar para o conteúdo

Automorfismo de grafos

Origem: Wikipédia, a enciclopédia livre.

No campo da matemática da teoria dos grafos, um automorfismo de um grafo é uma forma de simetria em que o grafo é mapeado em si, preservando a conectividade vértice-aresta.

Formalmente, um automorfismo de um grafo G = (V,E) é uma permutação σ do conjunto de vértices V, tal que para qualquer aresta e = (u,v), σ(e) = (σ(u),σ(v)) é também uma aresta. Ou seja, ele é um isomorfismo de grafos de G para ele mesmo.[1] Automorfismos podem ser definidos dessa maneira, tanto para grafos orientados quando para grafos não orientados.

A composição de dois automorfismos é outro automorfismo, e o conjunto de automorfismos de um grafo dado, sob a operação de composição, forma uma grupo, o grupo de automorfismo do grafo. No sentido inverso, pelo teorema de Frucht, todos os grupos podem ser representados como o grupo de automorfismo de um grafo conexo. - Na verdade, de um grafo cúbico.[2][3]

Complexidade computacional

[editar | editar código-fonte]

Construir o grupo de automorfismo é pelo menos tão difícil (em termos de complexidade computacional) quanto resolver o problema do isomorfismo de grafos, para determinar se dois grafos dados correspondem vértice com vértice e aresta com aresta. Pois, G e H são isomorfos se e somente se o grafo desconectado formado pelo união disjunta de grafos G e H tem um automorfismo que troca os dois componentes.[4]

Este desenho do grafo de Petersen mostra um subgrupo de suas simetrias, isomorfo ao grupo diedro D5, mas o grafo tem simetrias adicionais que não estão presentes no desenho(uma vez que o grafo é simétrico, todas as ligações são equivalentes, por exemplo).

O problema do automorfismo de grafos é o problema de testar se um grafo tem um automorfismo não trivial. Ele pertence à classe NP de problemas de complexidade computacional. Semelhantemente ao problema do isomorfismo de grafos, não se sabe se ele tem um algoritmo que o resolva em tempo polinomial ou se é NP-completo. Sabe-se que o problema do automorfismo de grafos é redutível muitos-para-um em tempo polinomial para o problema do isomorfismo de grafos, mas a redução inversa é desconhecida.[5][6]

Exibindo a Simetria

[editar | editar código-fonte]

Vários pesquisadores de desenho de grafos têm investigado algoritmos para desenhar grafos de tal forma que o automorfismo do grafo se torne visível como simetrias do desenho. Isso pode ser feito usando um método que não é projetado em torno de simetrias, mas que gera automaticamente os desenhos simétricos, quando possível,[7] ou explicitamente identificand as simetrias e usando-as para orientar a colocação de vértice no desenho.[8] Nem sempre é possível mostrar todas as simetrias do grafo, simultaneamente, de modo que talvez seja necessário escolher quais simetrias mostrar e quais deixar sem visualização.

Famílias de grafos definidas pelos seus automorfismos

[editar | editar código-fonte]

Várias famílias de grafos são definidas por terem certos tipos de automorfismos:

  • Um Grafo assimétrico é um grafo não direcionado, sem qualquer automorfismo não trivial.
  • Um Grafo vértice-transitivo é um grafo não direcionado em que cada vértice pode ser mapeado por um automorfismo em qualquer outro vértice.
  • Um Grafo aresta-transitivo é um grafo não direcionado em que cada aresta pode ser mapeada por um automorfismo em qualquer outra aresta.
  • Um Grafo simétrico é um grafo tal que cada par de vértices adjacentes podem ser mapeados por um automorfismo em qualquer outro par de vértices adjacentes.
  • Um Grafo distância-transitivo é um grafo tal que cada par de vértices pode ser mapeada por um automorfismo em qualquer outro par de vértices que estão à mesma distância.
  • Um Grafo semi-simétrico é um grafo que é aresta-transitivo, mas não vértice-transitivo.
  • Um Grafo meio-transitivo é um grafo que é vértice-transitivo e aresta-transitivo mas não simétrico.
  • Um Grafo anti-simétrico é um grafo dirigido, juntamente com uma permutação σ sobre os vértices que mapeia as arestas para arestas, mas inverte o sentido de cada aresta. Adicionalmente, σ necessita ser uma involução.

Relações de inclusão entre estas famílias estão indicadas no quadro seguinte:

Esqueleto de um Dodecaedro
Esqueleto de um Dodecaedro
Grafo de Shrikhande
Grafo de Shrikhande
Grafo de Paley
Grafo de Paley
distância-transitivo distância-regular fortemente regular
Grafo F26A
Grafo F26A
Grafo Nauru
Grafo Nauru
simétrico(arco-transitivo) t-transitivo, t ≥ 2
(se conectado)
Grafo de Holt
Grafo de Holt
Grafo de Folkman
Grafo de Folkman
Grafo completo bipartido K3,5
Grafo completo bipartido K3,5
transitivo nos vértices e nas arestas aresta-transitivo e regular aresta-transitivo
Esqueleto do Tetraedro truncado
Esqueleto do Tetraedro truncado
Grafo de Frucht
Grafo de Frucht
vértice-transitivo regular
Esqueleto do prisma triangular
Esqueleto do prisma triangular
Grafo de Cayley

Referências

  1. GALLIAN, Joseph A. (1994). Contemporary Abstract Algebra. Lexington, Massachusetts: D. C. Heath. ISBN 0-669-33907-5 
  2. Frucht, R. (1938), «Herstellung von Graphen mit vorgegebener abstrakter Gruppe.», Compositio Mathematica, ISSN 0010-437X (em alemão), 6: 239–250 .
  3. Frucht, R. (1949), «Graphs of degree three with a given abstract group», Canadian Journal of Mathematics, ISSN 0008-414X, 1: 365–378, MR0032987 
  4. Luks, Eugene M. (1982), «Isomorphism of graphs of bounded valence can be tested in polynomial time», Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5 .
  5. Köbler, Johannes; Uwe Schöning, Jacobo Torán (1993). «Graph Isomorphism Problem: The Structural Complexity». Birkhäuser Verlag. ISBN 0817636803. OCLC 246882287 
  6. Torán, Jacobo (2004). «On the Hardness of Graph Isomorphism» (PDF). SIAM Journal on Computing. pp. 1093–1108. doi:10.1137/S009753970241096X 
  7. Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), «Area requirement and symmetry display of planar upward drawings», Discrete and Computational Geometry, 7 (1): 381–401, doi:10.1007/BF02187850 ; Eades, Peter; Lin, Xuemin (2000), «Spring algorithms and symmetry», Theoretical Computer Science, 240 (2): 379–405, doi:10.1016/S0304-3975(99)00239-X .
  8. Hong, Seok-Hee (2002), «Drawing graphs symmetrically in three dimensions», Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, 2265, Springer-Verlag, pp. 106–108, doi:10.1007/3-540-45848-4_16 .