stringtranslate.com

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 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]

Complejidad computacional

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 .

Este dibujo del grafo de Petersen muestra un subgrupo de sus simetrías, isomorfo al grupo diedro D 5 , pero el grafo tiene simetrías adicionales que no están presentes en el dibujo. Por ejemplo, dado que el grafo es simétrico , todas las aristas son equivalentes.

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]

Algoritmos, software y aplicaciones

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.

Visualización de simetría

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.

Familias de grafos definidas por sus automorfismos

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:

Véase también

Referencias

  1. ^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (en alemán), 6 : 239–250, ISSN  0010-437X, Zbl  0020.07804.
  2. ^ Frucht, R. (1949), "Gráficos de grado tres con un grupo abstracto dado" (PDF) , Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153/CJM-1949-033-6 , ISSN  0008-414X, MR  0032987, S2CID 124723321 , archivado desde el original el 9 de junio de 2012 .
  3. ^ ab Mathon, R. (1979). "Una nota sobre el problema de conteo de isomorfismos de grafos". Information Processing Letters . 8 (3): 131–132. doi :10.1016/0020-0190(79)90004-8.
  4. ^ Dona, Daniele; Bajpai, Jitendra; Helfgott, Harald Andrés (12 de octubre de 2017). "Isomorfismos de grafos en tiempo cuasi-polinomial". arXiv : 1710.04574 [math.GR].
  5. ^ ab Lubiw, Anna (1981), "Algunos problemas NP-completos similares al isomorfismo de grafos", SIAM Journal on Computing , 10 (1): 11–21, doi :10.1137/0210002, MR  0605600.
  6. ^ Luks, Eugene M. (1982), "El isomorfismo de gráficos de valencia acotada se puede probar en tiempo polinomial", Journal of Computer and System Sciences , 25 (1): 42–65, doi :10.1016/0022-0000(82)90009-5.
  7. ^ Kobler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), Problema del isomorfismo de grafos: la complejidad estructural , Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC  246882287
  8. ^ ab Torán, Jacobo (2004). "Sobre la dureza del isomorfismo de grafos" (PDF) . SIAM Journal on Computing . 33 (5): 1093–1108. doi :10.1137/S009753970241096X. Archivado desde el original (PDF) el 20 de noviembre de 2008 . Consultado el 10 de marzo de 2010 .
  9. ^ McKay, Brendan (1981), "Practical Graph Isomorphism" (PDF) , Congressus Numerantium , 30 : 45–87 , consultado el 14 de abril de 2011 .
  10. ^ Junttila, Tommi; Kaski, Petteri (2007), "Diseñar una herramienta de etiquetado canónico eficiente para gráficos grandes y dispersos" (PDF) , Actas del Noveno Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX07) .
  11. ^ Darga, Paul; Sakallah, Karem; Markov, Igor L. (junio de 2008), "Descubrimiento de simetría más rápido usando escasez de simetrías", Actas de la 45.ª Conferencia anual de automatización del diseño (PDF) , págs. 149-154, doi :10.1145/1391469.1391509, ISBN 978-1-60558-115-6, S2CID  15629172, archivado desde el original (PDF) el 2021-01-26 , consultado el 2011-04-14 .
  12. ^ Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (julio de 2010), "Simetría y satisfacibilidad: una actualización" (PDF) , Proc. Simposio sobre satisfacibilidad (SAT) .
  13. ^ Di Battista, Giuseppe; Tamassia, Roberto ; Tollis, Ioannis G. (1992), "Requisito de área y visualización de simetría de dibujos planos ascendentes", Geometría discreta y computacional , 7 (1): 381–401, doi : 10.1007/BF02187850; Eades, Peter ; Lin, Xuemin (2000), "Algoritmos de primavera y simetría", Theoretical Computer Science , 240 (2): 379–405, doi :10.1016/S0304-3975(99)00239-X.
  14. ^ Hong, Seok-Hee (2002), "Dibujo de gráficos simétricamente en tres dimensiones", Proc. 9th Int. Symp. Graph Drawing (GD 2001) , Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, págs. 106-108, doi : 10.1007/3-540-45848-4_16 , ISBN 978-3-540-43309-5.

Enlaces externos