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 una gráfica 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 composicionde 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 . [1] [2]
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. [3] De hecho, solo contar los automorfismos es equivalente en tiempo polinómico al isomorfismo de grafos. [4]
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 . [5] 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. [3] 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. [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]
Algoritmos, software y aplicaciones
Si bien no se conocen algoritmos de tiempo polinomial 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 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 , [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 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 de Graph Automorphism incluyen el dibujo de gráficos y otras tareas de visualización, resolviendo instancias estructuradas de Satisfabilidad 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 alrededor de 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 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.
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:
distancia-transitiva | distancia regular | muy regular | ||
simétrico (arco-transitivo) | t -transitivo, t ≥ 2 | |||
(si está conectado) | ||||
vértice y borde transitivo | edge-transititive y regular | borde transitivo | ||
vértice-transitivo | regular | |||
Gráfico de Cayley |
Ver también
- Teoría de grafos algebraicos
- Coloración distintiva
Referencias
- ^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe" , Compositio Mathematica (en alemán), 6 : 239-250, ISSN 0010-437X , Zbl 0020.07804.
- ^ Frucht, R. (1949), "Gráficos de grado tres con un grupo de resumen dado" , Canadian Journal of Mathematics , 1 (4): 365–378, doi : 10.4153 / CJM-1949-033-6 , ISSN 0008-414X , MR 0032987.
- ^ a b Luks, Eugene M. (1982), "El isomorfismo de gráficos de valencia limitada se puede probar en tiempo polinomial", Journal of Computer and System Sciences , 25 (1): 42-65, doi : 10.1016 / 0022-0000 (82) 90009-5.
- ^ a b Mathon, R. (1979). "Una nota sobre el problema de conteo de isomorfismo gráfico". Cartas de procesamiento de información . 8 : 131-132. doi : 10.1016 / 0020-0190 (79) 90004-8 .
- ^ a b 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.
- ^ Köbler, Johannes; Schöning, Uwe ; Torán, Jacobo (1993), Problema de isomorfismo gráfico: la complejidad estructural , Birkhäuser Verlag , ISBN 0-8176-3680-3, OCLC 246882287
- ^ a b Torán, Jacobo (2004). "Sobre la dureza del isomorfismo gráfico" (PDF) . Revista SIAM de Computación . 33 : 1093-1108. doi : 10.1137 / S009753970241096X .
- ^ McKay, Brendan (1981), "Practical Graph Isomorphism" (PDF) , Congressus Numerantium , 30 : 45–87 , consultado el 14 de abril de 2011 .
- ^ Junttila, Tommi; Kaski, Petteri (2007), "Ingeniería de una herramienta de etiquetado canónica eficiente para gráficos grandes y dispersos" (PDF) , Actas del Noveno Taller sobre Ingeniería de Algoritmos y Experimentos (ALENEX07) .
- ^ Darga, Paul; Sakallah, Karem; Markov, Igor L. (junio de 2008), "Faster Symmetry Discovery using Sparsity of Symmetries" (PDF) , Actas de la 45ª Conferencia de automatización del diseño : 149-154, doi : 10.1145 / 1391469.1391509 , ISBN 978-1-60558-115-6.
- ^ Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (julio de 2010), "Simetría y satisfacción: una actualización" (PDF) , Proc. Simposio de satisfacción (SAT) .
- ^ Di Battista, Giuseppe; Tamassia, Roberto ; Tollis, Ioannis G. (1992), "Requisito de área y visualización de simetría de dibujos planos hacia arriba", Geometría discreta y computacional , 7 (1): 381–401, doi : 10.1007 / BF02187850; Eades, Peter ; Lin, Xuemin (2000), "Algoritmos de primavera y simetría", Informática teórica , 240 (2): 379–405, doi : 10.1016 / S0304-3975 (99) 00239-X.
- ^ Hong, Seok-Hee (2002), "Dibujar gráficos simétricamente en tres dimensiones", Proc. 9º Int. Symp. Graph Drawing (GD 2001) , Lecture Notes in Computer Science, 2265 , Springer-Verlag, págs. 106–108, doi : 10.1007 / 3-540-45848-4_16 , ISBN 978-3-540-43309-5.
enlaces externos
- Weisstein, Eric W. "Automorfismo gráfico" . MathWorld .