Automorfismo gráfico - Graph automorphism
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 conserva la conectividad borde-vértice.
Formalmente, un automorfismo de un gráfico G = ( V , E ) es una permutación σ del conjunto de vértices V , de manera 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 automorfismo de un gráfico conectado, de hecho, de un gráfico cúbico .
Complejidad computacional
Construir el grupo de automorfismos es al menos tan difícil (en términos de su complejidad computacional ) como resolver el problema de isomorfismo de grafos , determinando si dos grafos dados corresponden vértice por vértice y borde por borde. Porque, G y H son isomorfos si y solo 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. De hecho, solo contar los automorfismos es equivalente en tiempo polinomial al isomorfismo gráfico.
El problema del automorfismo de grafos es el problema de probar si un grafo tiene un automorfismo no trivial. Pertenece a la clase NP de complejidad computacional. Similar al problema del isomorfismo de grafos, se desconoce si tiene un algoritmo de tiempo polinomial o es NP-completo . Existe un algoritmo de tiempo polinomial para resolver el problema de automorfismo de grafos para grafos donde los grados de vértice están limitados por una constante. El problema del automorfismo del gráfico es polinomial-tiempo muchos-uno reducible al problema del isomorfismo del gráfico, pero se desconoce la reducción inversa. 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 .
Algoritmos, software y aplicaciones
Si bien no se conocen algoritmos de tiempo polinómico del 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 irredundante de generadores) para muchos gráficos grandes que surgen en las aplicaciones. Varias herramientas de software de código abierto están disponibles para esta tarea, incluidas NAUTY , BLISS y SAUCY . SAUCY y BLISS son particularmente eficientes para gráficos dispersos, por ejemplo, SAUCY procesa algunos gráficos con millones de vértices en solo segundos. Sin embargo, BLISS y NAUTY también pueden producir etiquetado canónico , mientras que SAUCY está optimizado actualmente para resolver Graph Automorphism. Una observación importante es que para un gráfico en n vértices, el grupo de automorfismo puede ser especificado por no más de n-1 generadores, y los paquetes de software anteriores están garantizados para satisfacer este límite como un efecto secundario de sus algoritmos (conjuntos mínimos de los 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 , que 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 Gráfico incluyen el dibujo de gráficos y otras tareas de visualización, resolviendo instancias estructuradas de Satisfacción Booleana que surgen en el contexto de Verificación Formal y Logística . La simetría molecular puede predecir o explicar las propiedades químicas.
Pantalla de simetría
Varios de dibujo gráfico investigadores han investigado algoritmos para dibujar gráficos de tal manera que los automorfismos de la gráfica se hacen visibles como simetrías del dibujo. Esto se puede hacer 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, o identificando explícitamente simetrías y usándolas para guiar la ubicación de los vértices en el dibujo. 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.
Familias de gráficos definidas por sus automorfismos
Varias familias de gráficos se definen por tener ciertos tipos de automorfismos:
- Un gráfico asimétrico es un gráfico no dirigido con solo el automorfismo trivial.
- Un gráfico de vértice transitivo es un gráfico no dirigido en el que cada vértice puede ser mapeado por un automorfismo en cualquier otro vértice.
- Un gráfico de borde transitivo es un gráfico no dirigido en el que cada borde puede ser mapeado por un automorfismo en cualquier otro borde.
- Un gráfico simétrico es un gráfico tal que cada par de vértices adyacentes puede ser mapeado por un automorfismo en cualquier otro par de vértices adyacentes.
- Un gráfico de distancia-transitiva es un gráfico tal que cada par de vértices puede ser mapeado por un automorfismo en cualquier otro par de vértices que estén separados a la misma distancia.
- Un gráfico semi-simétrico es un gráfico que es transitivo por aristas pero no transitivo por vértices.
- Un gráfico semitransitivo es un gráfico que es transitivo de vértice y transitivo de borde, pero no simétrico.
- Un gráfico de simetría sesgada es un gráfico dirigido junto con una permutación σ en los vértices que asigna bordes a bordes pero invierte la dirección de cada borde. Además, se requiere que σ sea una involución .
Las relaciones de inclusión entre estas familias se indican en la siguiente tabla:
