En el campo matemático de la teoría de grafos , un automorfismo de un gráfico es una forma de simetría en la que el gráfico se asigna a sí mismo preservando la conectividad borde- 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 gráfico de G a sí mismo. Los automorfismos se pueden definir de esta manera tanto para gráficos dirigidos como para gráficos no dirigidos . La composición de dos automorfismos es otro automorfismo, y el conjunto de automorfismos de un gráfico dado, bajo la operación de composición, forma un grupo , el grupo de automorfismos del gráfico. En la dirección opuesta, según el teorema de Frucht , todos los grupos pueden representarse como el grupo de automorfismos de un gráfico conexo; de hecho, de un gráfico cúbico . [1] [2]
Construir el grupo de automorfismo es al menos tan difícil (en términos de su complejidad computacional ) como resolver el problema de isomorfismo de gráficos , determinando si dos gráficos dados corresponden vértice por vértice y borde por borde. Porque, G y H son isomorfos si y sólo si el gráfico desconectado formado por la unión disjunta de los gráficos G y H tiene un automorfismo que intercambia los dos componentes. [3] De hecho, simplemente contar los automorfismos es equivalente en tiempo polinomial al isomorfismo del gráfico. [4]
El problema del automorfismo de grafos es el problema de probar si un gráfico tiene un automorfismo no trivial. Pertenece a la clase NP de complejidad computacional. Similar al problema de isomorfismo gráfico, se desconoce si tiene un algoritmo de tiempo polinómico o si es NP-completo . [5] Existe un algoritmo de tiempo polinómico para resolver el problema de automorfismo de gráficos en los que los grados de los vértices están acotados por una constante. [3] El problema del automorfismo del gráfico es reducible en tiempo polinomial muchos-uno al problema del isomorfismo del gráfico, pero se desconoce la reducción inversa. [4] [6] [7] Por el contrario, la dureza se conoce cuando los automorfismos están restringidos de cierta manera; 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] [7]
Si bien no se conocen algoritmos de tiempo polinómico en el peor de los casos para el problema general del automorfismo de gráficos, es bastante fácil encontrar el grupo de automorfismo (e imprimir un conjunto irreundante de generadores) para muchos gráficos grandes que surgen en las aplicaciones. Hay varias herramientas de software de código abierto disponibles para esta tarea, incluidas NAUTY, [8] BLISS [9] y SAUCY. [10] [11] SAUCY y BLISS son particularmente eficientes para gráficos dispersos, por ejemplo, SAUCY procesa algunos gráficos con millones de vértices en cuestión de segundos. Sin embargo, BLISS y NAUTY también pueden producir etiquetado canónico , mientras que SAUCY está actualmente optimizado para resolver el automorfismo de gráficos. Una observación importante es que para un gráfico en n vértices, el grupo de automorfismo no puede especificarse mediante más que generadores, y se garantiza que los paquetes de software anteriores satisfarán este límite como efecto secundario de sus algoritmos (los conjuntos mínimos de generadores son más difíciles). 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, hasta marzo de 2012.
Las aplicaciones prácticas del automorfismo de gráficos incluyen el dibujo de gráficos y otras tareas de visualización, resolviendo instancias estructuradas de satisfacibilidad booleana que surgen en el contexto de verificación formal y logística . La simetría molecular puede predecir o explicar propiedades químicas.
Varios investigadores de dibujo de gráficos han investigado algoritmos para dibujar gráficos de tal manera que los automorfismos del gráfico se vuelven visibles como simetrías del dibujo. Esto se puede hacer utilizando un método que no esté diseñado en torno a simetrías, pero que genere automáticamente dibujos simétricos cuando sea posible, [12] o identificando explícitamente simetrías y usándolas para guiar la ubicación de los vértices en el dibujo. [13] No siempre es posible mostrar todas las simetrías del gráfico 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:
