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.
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. 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.
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.
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:
