Gráfico sesgado simétrico

Un gráfico sesgado simétrico es un gráfico dirigido isomorfo a su propio gráfico transpuesto . Este gráfico se forma invirtiendo todos los arcos con isomorfismo y es una involución sin puntos fijos . Los gráficos sesgados simétricos son idénticos a las cubiertas dobles de los gráficos bidireccionales .

Los gráficos sesgados simétricos se introdujeron por primera vez con el nombre de dígrafos antisimétricos por Tutt [1] , luego con el nombre de gráficos de doble cobertura de gráficos polares que fueron utilizados por Zelinka [2] , y más tarde con el nombre de gráficos de doble cobertura de gráficos bidireccionales utilizado por Zaslavsky [3] . Surgen, por ejemplo, en el modelado de la búsqueda de caminos y ciclos alternos , en algoritmos para encontrar coincidencias en gráficos para pruebas, en el problema de descomponer una configuración en el Juego de la Vida en componentes más pequeños, en el problema de visualización de gráficos y en el problema de construir gráficos de salida .utilizado para resolver eficientemente el problema de 2-satisfacibilidad .

Definición

Como lo definen, por ejemplo, Goldberg y Karzanov [4] , un grafo asimétrico es un grafo dirigido junto con una función que asigna los vértices del grafo a sus otros vértices y satisface las propiedades: $GRAMO$ $\sigma$ $GRAMO$

Para cualquier parte superior ${\ Displaystyle v, \ sigma (v) \ neq v}$
Para cualquier parte superior $v,\sigma (\sigma (v))=v$
Porque todo arco debe ser también un arco. ${\ estilo de visualización (u, v), (\ sigma (v), \ sigma (u))}$

Puede usar la tercera propiedad para extenderla a la función de inversión de la orientación del arco del gráfico . $\sigma$ $GRAMO$

El gráfico transpuesto de un gráfico es el gráfico formado al invertir cada borde del gráfico y define un isomorfismo del gráfico transpuesto. Sin embargo, para un gráfico sesgado simétrico, existe un requisito adicional de que el isomorfismo lleve cada vértice a otro vértice sin permitir que un vértice se asigne a sí mismo o que agrupe más de dos vértices en un ciclo de isomorfismo. $GRAMO$ $GRAMO$ $\sigma$ $GRAMO$

Se dice que una ruta o ciclo en un gráfico simétrico sesgado es regular si, para cada vértice de la ruta o ciclo, el vértice correspondiente no es parte de la ruta o ciclo. $v$ ${\ estilo de visualización \ sigma (v)}$

Ejemplos

Cualquier camino orientado con un número par de vértices es sesgado simétrico, de acuerdo con la simetría que intercambia los dos extremos del camino. Sin embargo, las rutas con un número impar de vértices no son simétricas oblicuas porque la simetría de orientación inversa de este gráfico mapea el vértice central de este gráfico en sí mismo, lo que no está permitido para los gráficos simétricos oblicuos.

De manera similar, un ciclo orientado es asimétrico si y solo si tiene un número par de vértices. En este caso, el número de aplicaciones diferentes que implementan la simetría oblicua del gráfico es igual a la mitad de la duración del ciclo. $\sigma$

Gráficos polares y flechas de ruta, gráficos de doble cubierta y gráficos bidireccionales

Un gráfico asimétrico se puede definir de manera equivalente como un gráfico de una doble cubierta de un gráfico polar (introducido por Zelinka [5] [6] , y Cook llamó gráficos de flecha de ruta [7] [8] ), que son gráficos no dirigidos y en el que las aristas adyacentes a cada vértice se dividen en dos subconjuntos. Cada vértice de un gráfico polar corresponde a dos vértices de un gráfico simétrico sesgado, y cada borde de un gráfico polar corresponde a dos bordes de un gráfico simétrico sesgado. Esta equivalencia fue utilizada por Goldberg y Karzanov [4] para modelar problemas de correspondencia en términos de gráficos sesgados simétricos. En tal aplicación, los dos subconjuntos de aristas en cada vértice son aristas coincidentes y no coincidentes. Zelinka (según F. Zaitek) y Cook visualizaron los vértices del gráfico polar como puntos donde confluyen varias vías de ferrocarril si un tren entra en un cambio de vía en una vía de ferrocarril que viene de una dirección, debe salir por la vía en el otra dirección. El problema de encontrar curvas suaves que no se corten a sí mismas entre puntos dados de una vía férrea surge al verificar si algún tipo de visualización de gráfico es admisible [9] , y se puede modelar como encontrar un camino regular en un gráfico sesgado simétrico.

Un concepto estrechamente relacionado es el gráfico bidireccional Edmonds y Johnson [10] (un "gráfico polarizado" en la terminología de Zelinka [5] [6] ), un gráfico en el que cada uno de los dos vértices de cualquier borde puede ser el principio o el final, independientemente de otro pico. Un gráfico bidireccional se puede interpretar como un gráfico polar si los bordes de cada vértice se dividen según la orientación del borde en ese vértice: el principio o el final. Sin embargo, el intercambio de roles de comienzos y finales en un vértice separado ("cambio" de un vértice en la terminología de Zaslavsky [3] ) da otro gráfico bidireccional, pero el mismo gráfico polar.

Para conocer la correspondencia entre los gráficos bidireccionales y los gráficos sesgados simétricos, consulte Zaslavsky [11] o Babenko [12] .

Para formar un gráfico de doble cubierta (es decir, el gráfico sesgado simétrico correspondiente) a partir de un gráfico polar , creamos dos vértices de cada vértice del gráfico , y , y sea . Para cada borde del gráfico , cree dos bordes dirigidos en el gráfico de cobertura, uno desde hasta y otro desde hasta . Si está en el primer subconjunto de aristas en , estos dos arcos van de a y de a , pero si pertenece a otro subconjunto, los arcos serán de a y de a . Por el contrario, dado un gráfico sesgado simétrico , se puede formar un gráfico polar que tiene un vértice para cualquier par de vértices correspondientes en el gráfico y una arista no dirigida para cada par de aristas correspondientes en . Los bordes no dirigidos en cada vértice del gráfico polar se pueden dividir en dos subconjuntos según el vértice del gráfico original que sale y entra el arco. $GRAMO$ $v$ $GRAMO$ $v_{0}$ $v_{1}$ ${\ estilo de visualización \ sigma (v_ {i}) = v_ {1-i}}$ ${\ estilo de visualización e = (u, v)}$ $GRAMO$ $tu$ $v$ $v$ $tu$ $mi$ $v$ $tu_{0}$ $v_{0}$ $v_{1}$ $tu_{1}$ $mi$ $tu_{0}$ $v_{1}$ $v_{0}$ $tu_{1}$ $GRAMO$ $GRAMO$ $GRAMO$

Una ruta o ciclo regular en un gráfico sesgado simétrico corresponde a una ruta o ciclo en un gráfico polar que usa como máximo un borde de cada subconjunto de bordes en cada uno de sus vértices.

Coincidencia

Al construir una coincidencia en un gráfico no dirigido, es importante encontrar un camino alterno , un camino a través de vértices que comienza y termina en vértices que no pertenecen a la coincidencia, y cuyos bordes en posiciones impares de la ruta no pertenecen a este coincidencia parcial, y cuyos bordes en posiciones pares del camino son bordes de la coincidencia. Al eliminar de la coincidencia los bordes de esa ruta que pertenecen a la coincidencia y agregarle los bordes restantes de la ruta, se puede aumentar el tamaño de la coincidencia. De manera similar, los ciclos que alternan entre bordes coincidentes y no coincidentes son importantes en los problemas de coincidencia ponderados. Como han demostrado Goldberg y Karzanov [4] , una ruta o ciclo alternativo en un gráfico no dirigido se puede modelar como una ruta o ciclo regular en un gráfico dirigido sesgado simétrico. Para crear un gráfico sesgado simétrico a partir de un gráfico no dirigido con una coincidencia dada , considere el gráfico como un gráfico de flecha en el que los bordes en cada vértice se dividen en pertenecientes y no pertenecientes a la combinación. Un camino alterno en un gráfico es entonces un camino regular en ese gráfico de flechas, y un ciclo alterno en el gráfico es un ciclo regular en el gráfico de flechas. $GRAMO$ $METRO$ $GRAMO$ $GRAMO$ $GRAMO$

Goldberg y Karzanov [4] generalizaron algoritmos de caminos alternos para mostrar que la existencia de un camino regular entre dos vértices cualesquiera de un gráfico asimétrico sesgado puede verificarse en tiempo lineal. Si, además, se da una función de longitud no negativa en los bordes del gráfico que asigna longitudes iguales a un borde y un borde , el camino regular más corto que conecta un par dado de nodos en un gráfico sesgado simétrico con bordes y vértices se puede encontrar en el tiempo . Si la función de longitud puede tomar valores negativos, se puede verificar la existencia de un ciclo regular negativo en tiempo polinomial . $mi$ ${\ estilo de visualización \ sigma (e)}$ $metro$ $norte$ $O(m\log n)$

Además de los problemas con las trayectorias que surgen cuando se trabaja con coincidencias, también se estudiaron las generalizaciones sesgadas simétricas del flujo máximo y el teorema de corte mínimo [1] [13] .

Teoría del Juego de la Vida

Cook [8] demostró que una configuración en el Juego de la Vida se puede dividir en dos configuraciones más pequeñas si y solo si el gráfico de la flecha de viaje asociada contiene un ciclo regular. Para gráficos de flechas que no contengan más de tres aristas por vértice, esto se puede verificar en tiempo polinomial eliminando uno a uno los puentes (aristas cuya eliminación hace que el gráfico se desconecte) y los vértices en los que todas las aristas pertenecen a la misma parte de la partición, mientras que existe la posibilidad de implementar tales simplificaciones. Si el resultado es un gráfico vacío, no hay un ciclo regular en el gráfico. De lo contrario, se puede encontrar un ciclo regular en cualquier componente no puenteado. La búsqueda de puentes en este algoritmo se puede realizar de manera eficiente utilizando el algoritmo dinámico de Sorup [14] . Gabov, Kaplan y Tarjan [15] consideraron previamente una técnica similar para eliminar puentes en el contexto de coincidencias .

Factibilidad

El problema de 2-satisfacibilidad , es decir, una expresión en forma normal conjuntiva con dos variables o su negación, se puede transformar en un gráfico de salida reemplazando cada expresión con dos implicaciones y . En este gráfico, cada vértice representa una variable o su negación, y cada arista dirigida representa una implicación. El gráfico es por construcción sesgado-simétrico con una función que asigna cada variable a su negación. Como han demostrado Asvall, Plass y Tarjan [16] , encontrar un conjunto satisfactorio de valores para una instancia de un problema de satisfacibilidad 2 es equivalente a dividir este gráfico de salida en dos subconjuntos de vértices, y , de modo que no comience ningún arco. en y termina en . Si existe tal división, se puede obtener un conjunto satisfactorio de valores asignando un valor Verdadero a cada variable en y un valor Falso a cada variable en . Esto se puede hacer si y solo si ningún componente fuertemente conectado del gráfico contiene tanto un vértice como su vértice complementario . Si dos vértices pertenecen a la misma componente fuertemente conectada, las variables correspondientes o sus negaciones son necesariamente iguales entre sí en cualquier conjunto de valores satisfactorio de una instancia del problema de 2 satisfacibilidad. El tiempo total de verificación de una fuerte conectividad y encontrar una partición del gráfico de salida es lineal en el tamaño de una expresión 2-CNF determinada. ${\ estilo de visualización u \ lo v}$ $(\lnot u)\Rightarrow v$ $(\lnot v)\Rightarrow u$ $\sigma$ $S$ ${\ estilo de visualización \ sigma (S)}$ $S$ ${\ estilo de visualización \ sigma (S)}$ $S$ ${\ estilo de visualización \ sigma (S)}$ $v$ ${\ estilo de visualización \ sigma (v)}$

Reconocimiento

El problema de reconocer si un gráfico dirigido dado es asimétrico es NP-completo . Esto se deduce del resultado de Lalonde [17] de que el problema de encontrar una involución de inversión de color en un gráfico bipartito es NP-completo si y solo si el gráfico dirigido dado por la orientación de cada borde de una clase de color a otra es asimétrico. . Esta complejidad no afecta a los algoritmos de búsqueda de rutas para gráficos simétricos oblicuos, ya que estos algoritmos asumen que la estructura simétrica oblicua se proporciona como parte de la entrada del algoritmo, en lugar de derivarse del gráfico solo.

Notas

↑ 1 2 Tutte, 1967 .
↑ Zelinka, 1976b .
↑ 12 Zaslavski , 1991 .
↑ 1 2 3 4 Goldberg, Karzanov, 1996 .
↑ 1 2 Zelinka, 1974 .
↑ 12 Zelinka , 1976a .
↑ El gráfico de participación proviene de la representación del gráfico como análogo a las vías del tren, con los cruces de ramales individuales como flechas de cambio.
↑ 12 Cook , 2003 .
↑ Hui, Schaefer, Stefankovič, 2004 .
↑ Edmonds, Johnson, 1970 .
↑ Zaslavsky, 1991 , pág. Sección 5.
↑ Babenko, 2006 .
↑ Goldberg, Karzanov, 2004 .
↑ Thorup, 2000 .
↑ Gabow, Kaplan, Tarjan, 1999 .
↑ Aspvall, Plass, Tarjan, 1979 .
↑ Lalonde, 1981 .

Literatura

Bengt Aspvall, Michael F. Plass, Robert E. Tarjan. Un algoritmo de tiempo lineal para probar la veracidad de ciertas fórmulas booleanas cuantificadas // Cartas de procesamiento de información. - 1979. - T. 8 , núm. 3 . — S. 121–123 . - doi : 10.1016/0020-0190(79)90002-4 .
Máximo A. Babenko. Gráficos acíclicos bidirigidos y sesgados simétricos: algoritmos y estructura // Ciencias de la Computación - Teoría y Aplicaciones. - Springer-Verlag, 2006. - T. 3967. - S. 23-34. — (Apuntes de clase en informática). - ISBN 978-3-540-34166-6 . -doi : 10.1007/ 11753728_6 .
Norman L. Biggs. Teoría algebraica de grafos. — Londres: Cambridge University Press, 1974.
Mateo Cook. Teoría de la naturaleza muerta // Nuevas Construcciones en Autómatas Celulares. - Estudios del Instituto Santa Fe en Ciencias de la Complejidad, Oxford University Press, 2003. - pp. 93–118. .
Jack Edmonds, Ellis L. Johnson. Emparejamiento: una clase bien resuelta de programas lineales // Estructuras combinatorias y sus aplicaciones: Actas del Simposio de Calgary, junio de 1969. - Gordon y Breach, 1970. Reimpreso en "Optimización combinatoria - ¡Eureka, te encoges!", Springer-Verlag , Lecture Notes in Computer Science 2570, 2003, págs. 27-30, doi : 10.1007/3-540-36478-1_3 .
Harold N. Gabow, Haim Kaplan, Robert E. Tarjan . Algoritmos únicos de coincidencia máxima // Proc. 31º ACM Symp. Teoría de la Computación (STOC). - 1999. - S. 70-78. — ISBN 1-58113-067-8 . -doi : 10.1145/ 301250.301273 .
Andrew V. Goldberg, Alexander V. Karzanov. Problemas de ruta en gráficos sesgados simétricos // Combinatorica. - 1996. - T. 16 , núm. 3 . — S. 353–382 . -doi : 10.1007/ BF01261321 .
Andrew V. Goldberg, Alexander V. Karzanov. Máximos flujos y emparejamientos sesgados simétricos // Programación matemática. - 2004. - T. 100 , núm. 3 . — S. 537–568 . -doi : 10.1007 / s10107-004-0505-z . — arXiv : matemáticas/0304290 .
Peter Hui, Marcus Schaefer, Daniel Štefankovič. Vías de tren y dibujos confluentes // Proc. 12 Int. Síntoma Dibujo gráfico . - Springer-Verlag, 2004. - T. 3383. - S. 318-328. — (Apuntes de clase en informática).
François Lalonde. Le problème d'étoiles pour graphes est NP-complet // Matemática discreta. - 1981. - T. 33 , núm. 3 . — S. 271–280 . - doi : 10.1016/0012-365X(81)90271-5 .
Mikkel Thorup. Conectividad gráfica casi óptima totalmente dinámica [ sic ] // Proc. 32º Simposio ACM sobre Teoría de la Computación . - 2000. - S. 343-350 . — ISBN 1-58113-184-4 . -doi : 10.1145/ 335305.335345 .
Tutte WT Dígrafos antisimétricos // Canadian Journal of Mathematics. - 1967. - T. 19 . — S. 1101–1117 . -doi :/ CJM-1967-101-8 .
Thomas Zaslavski. Grafos con signo // Matemática Aplicada Discreta. - 1982. - T. 4 . — págs. 47–74 . - doi : 10.1016/0166-218X(82)90033-6 .
Thomas Zaslavski. Orientación de grafos firmados // European Journal of Combinatorics. - 1991. - T. 12 . — S. 361–375 . -doi : 10.1016 / s0195-6698(13)80118-7 .
Bohdan Zelinka. Gráficos polares y tráfico ferroviario // Aplikace Matematicy. - 1974. - T. 19 . — S. 169–176 .
Bohdan Zelinka. Isomorfismos de gráficos polares y polarizados // Revista matemática checoslovaca. — 1976a. - T. 26 . — S. 339–351 .
Bohdan Zelinka. Analoga del teorema de Menger para gráficos polares y polarizados // Revista matemática checoslovaca. — 1976b. - T. 26 . — S. 352–360 .