automorfismo de grafos

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, preservando la conectividad entre aristas y vértices .

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 ) forma una arista si y solo si el par ( σ ( u ), σ ( v )) también forma una arista. Es decir, es un isomorfismo de grafos 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 lista de generadores, es equivalente en tiempo polinomial al problema de isomorfismo de grafos y, por lo tanto, resoluble en tiempo cuasipolinomial , es decir, con tiempo de ejecución${\displaystyle 2^{O((\log n)^{c})}}$para algún fijo${\displaystyle c>0}$. ^{[ 3 ] [ 4 ]} En consecuencia, al igual que el problema del 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 sencillo de comprobar si un grafo tiene simetrías (automorfismos no triviales), conocido como el problema de automorfismos de grafos , tampoco tiene una solución conocida en tiempo polinomial . ^{[ 5 ]} Existe un algoritmo en tiempo polinomial para resolver el problema de automorfismos de grafos para grafos donde los grados de los vértices están acotados por una constante. ^{[ 6 ]} El problema de automorfismos de grafos es reducible en tiempo polinomial al problema de isomorfismos de grafos, pero la reducción inversa es desconocida. ^{[ 3 ] [ 7 ] [ 8 ]} Por el contrario, se conoce la dificultad cuando los automorfismos están restringidos de cierta manera; por ejemplo, determinar la existencia de un automorfismo sin puntos fijos (un automorfismo que no fija ningún vértice) es NP-completo, y el problema de contar tales automorfismos es ♯P-completo . ^{[ 5 ] [ 8 ]}

Aunque 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. Varias herramientas de software de código abierto están disponibles para esta tarea, incluyendo 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 apenas segundos. Sin embargo, BLISS y NAUTY también pueden producir etiquetado canónico , mientras que SAUCY está actualmente optimizado para resolver el problema de automorfismo de grafos. Una observación importante es que para un grafo con n vértices, el grupo de automorfismos se puede especificar con no más de${\displaystyle n-1}$Los generadores y los paquetes de software mencionados anteriormente garantizan el cumplimiento de este límite como efecto secundario de sus algoritmos (los conjuntos mínimos de generadores son más difíciles de encontrar y no resultan particularmente útiles en la práctica). Además, 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 del tiempo de ejecución de estos algoritmos. Sin embargo, esto no se ha establecido de forma concluyente hasta marzo de 2012.

Las aplicaciones prácticas del automorfismo de grafos incluyen el dibujo de grafos y otras tareas de visualización, así como la resolución de instancias estructuradas 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 en el campo del dibujo de grafos han estudiado algoritmos para dibujar grafos de manera que los automorfismos del grafo se hagan visibles como simetrías del dibujo. Esto puede lograrse mediante un método que no se base en simetrías, sino que genere automáticamente dibujos simétricos cuando sea posible ^{[ 13 ]} , o bien identificando explícitamente las simetrías y utilizándolas para guiar la colocación de los 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 grafos se definen por tener ciertos tipos de automorfismos:

• Un grafo asimétrico es un grafo no dirigido que solo posee el automorfismo trivial.
• Un grafo transitivo de vértices es un grafo no dirigido en el que cada vértice puede ser mapeado mediante un automorfismo en cualquier otro vértice.
• Un grafo transitivo por aristas es un grafo no dirigido en el que cada arista puede transformarse, mediante un automorfismo, en cualquier otra arista.
• Un grafo simétrico es un grafo tal que cualquier par de vértices adyacentes puede transformarse, mediante un automorfismo, en cualquier otro par de vértices adyacentes.
• Un grafo transitivo en distancia es un grafo tal que cualquier par de vértices puede transformarse, mediante un automorfismo, en cualquier otro par de vértices que estén a la misma distancia entre sí.
• Un grafo semisimétrico es un grafo que es transitivo en sus aristas pero no en sus vértices.
• Un grafo semitransitivo es un grafo que es transitivo en vértices y transitivo en aristas, pero no simétrico.
• Un grafo antisimétrico es un grafo dirigido con una permutación σ en los vértices que mapea aristas con aristas, pero invierte la dirección de cada arista. Además, se requiere que σ sea una involución .

Las relaciones de inclusión entre estas familias se indican en la siguiente tabla:

• Teoría algebraica de grafos
• Coloración distintiva

• Weisstein, Eric W. "Automorfismo de gráficos" . MundoMatemático .