Automorfismo de grafos

Na 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 é uma permutação σ do conjunto de vértices V, tal que para qualquer aresta , é também uma aresta. Ou seja, ele é um isomorfismo de grafos de G para ele mesmo. 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..

Complexidade computacional 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, e são isomorfos se e somente se o grafo desconectado formado pelo união disjunta de grafos e tem um automorfismo que troca os dois componentes.. thumb|direita|Este desenho do grafo de Petersen mostra um subgrupo de suas simetrias, isomorfo ao grupo diedro , 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.

Exibindo a Simetria 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,; . ou explicitamente identificand as simetrias e usando-as para orientar a colocação de vértice no desenho.. 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 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 semissimé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:

Categoria:Teoria dos grafos

de:Automorphismus#Graphen

Automorfismo de grafos

Źródło i licencja