En el campo matemático de la teoría de grafos , un automorfismo de un grafo es una forma de simetría en la que el grafo se mapea sobre sí mismo mientras se preserva la conectividad arista- vértice .
Formalmente, un automorfismo de un grafo G = ( V , E ) es una permutación σ del conjunto de vértices V , tal que el par de vértices ( u , v ) forman una arista si y solo si el par ( σ ( u ), σ ( v )) también forman una arista. Es decir, es un isomorfismo de grafo de G a sí mismo. Los automorfismos pueden definirse de esta manera tanto para grafos dirigidos como para grafos no dirigidos . La composición de dos automorfismos es otro automorfismo, y el conjunto de automorfismos de un grafo dado, bajo la operación de composición, forma un grupo , el grupo de automorfismos del grafo. En la dirección opuesta, por el teorema de Frucht , todos los grupos pueden representarse como el grupo de automorfismos de un grafo conexo – de hecho, de un grafo cúbico . [1] [2]
La construcción del grupo de automorfismos de un grafo, en forma de una lista de generadores, es equivalente en tiempo polinomial al problema de isomorfismo de grafos y, por lo tanto, resoluble en tiempo cuasi-polinomial , es decir, con tiempo de ejecución para algún . [3] [4] En consecuencia, al igual que el problema de isomorfismo de grafos, se sabe que el problema de encontrar el grupo de automorfismos de un grafo pertenece a la clase de complejidad NP , pero no se sabe que esté en P ni que sea NP-completo y, por lo tanto, puede ser NP-intermedio .
El problema más fácil de probar si un grafo tiene alguna simetría (automorfismos no triviales), conocido como el problema del automorfismo de grafos , tampoco tiene una solución de tiempo polinomial conocida . [5] Hay un algoritmo de tiempo polinomial para resolver el problema del automorfismo de grafos para grafos donde los grados de los vértices están acotados por una constante. [6] El problema del automorfismo de grafos es polinomial en tiempo muchos-uno reducible al problema del isomorfismo de grafos, pero la reducción inversa es desconocida. [3] [7] [8] Por el contrario, la dificultad se conoce cuando los automorfismos están restringidos de una manera determinada; por ejemplo, determinar la existencia de un automorfismo libre de punto fijo (un automorfismo que no fija ningún vértice) es NP-completo, y el problema de contar tales automorfismos es ♯P-completo . [5] [8]
Si bien no se conocen algoritmos de tiempo polinomial en el peor de los casos para el problema general de automorfismo de grafos, encontrar el grupo de automorfismos (e imprimir un conjunto irredundante de generadores) para muchos grafos grandes que surgen en aplicaciones es bastante fácil. Hay varias herramientas de software de código abierto disponibles para esta tarea, incluidas NAUTY, [9] BLISS [10] y SAUCY. [11] [12] SAUCY y BLISS son particularmente eficientes para grafos dispersos, por ejemplo, SAUCY procesa algunos grafos con millones de vértices en meros segundos. Sin embargo, BLISS y NAUTY también pueden producir etiquetado canónico , mientras que SAUCY está actualmente optimizado para resolver automorfismo de grafos. Una observación importante es que para un grafo en n vértices, el grupo de automorfismos puede especificarse por no más de generadores, y se garantiza que los paquetes de software anteriores satisfacen este límite como un efecto secundario de sus algoritmos (los conjuntos mínimos de generadores son más difíciles de encontrar y no son particularmente útiles en la práctica). También parece que el soporte total (es decir, el número de vértices movidos) de todos los generadores está limitado por una función lineal de n , lo cual es importante en el análisis en tiempo de ejecución de estos algoritmos. Sin embargo, esto no se ha establecido con certeza, a marzo de 2012.
Las aplicaciones prácticas del automorfismo de grafos incluyen el dibujo de grafos y otras tareas de visualización, la resolución de casos estructurados de satisfacibilidad booleana que surgen en el contexto de la verificación formal y la logística . La simetría molecular puede predecir o explicar propiedades químicas.
Varios investigadores del dibujo de grafos han investigado algoritmos para dibujar grafos de tal manera que los automorfismos del grafo se hagan visibles como simetrías del dibujo. Esto se puede hacer ya sea usando un método que no esté diseñado en torno a simetrías, pero que genere automáticamente dibujos simétricos cuando sea posible, [13] o identificando explícitamente simetrías y usándolas para guiar la colocación de vértices en el dibujo. [14] No siempre es posible mostrar todas las simetrías del grafo simultáneamente, por lo que puede ser necesario elegir qué simetrías mostrar y cuáles dejar sin visualizar.
Varias familias de gráficos se definen por tener ciertos tipos de automorfismos:
Las relaciones de inclusión entre estas familias se indican en la siguiente tabla:
