Loading AI tools
Da 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]
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]
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]
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.
Várias famílias de grafos são definidas por terem certos tipos de automorfismos:
Relações de inclusão entre estas famílias estão indicadas no quadro seguinte:
![]() |
![]() |
![]() |
![]() |
![]() |
distância-transitivo | distância-regular | fortemente regular | ||
![]() | ||||
![]() |
![]() |
![]() | ||
simétrico(arco-transitivo) | t-transitivo, t ≥ 2 | |||
![]() | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
transitivo nos vértices e nas arestas | aresta-transitivo e regular | aresta-transitivo | ||
![]() | ![]() | |||
![]() |
![]() |
![]() | ||
vértice-transitivo | regular | |||
![]() | ||||
![]() | ||||
Grafo de Cayley | ||||
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.