Gráfico de simetría oblicua

Familias de gráficos definidas por sus automorfismos
distancia-transitiva	→	distancia regular	←	muy regular
↓
simétrico (arco-transitivo)	←	t -transitivo, t  ≥ 2		simétrico sesgado
↓
(si está conectado) vértice y borde transitivo	→	edge-transititive y regular	→	borde transitivo
↓		↓		↓
vértice-transitivo	→	regular	→	(si es bipartito) birregular
↑
Gráfico de Cayley	←	simétrico cero		asimétrico

En la teoría de grafos , una rama de las matemáticas, un grafo simétrico sesgado es un grafo dirigido que es isomorfo a su propio grafo de transposición , el grafo formado invirtiendo todas sus aristas, bajo un isomorfismo que es una involución sin puntos fijos . Los gráficos de simetría oblicua son idénticos a los gráficos de doble cobertura de los gráficos bidireccionales .

Los gráficos de simetría sesgada fueron introducidos por primera vez bajo el nombre de dígrafos antisimétricos por Tutte (1967) , más tarde como los gráficos de doble cobertura de los gráficos polares por Zelinka (1976b) , y aún más tarde como los gráficos de doble cobertura de los gráficos bidireccionales por Zaslavsky (1991). . Surgen al modelar la búsqueda de caminos alternos y ciclos alternos en algoritmos para encontrar coincidencias en gráficos, al probar si un patrón de naturaleza muerta en el Juego de la vida de Conway puede dividirse en componentes más simples, en el dibujo de gráficos y en los gráficos de implicación utilizados para resolver eficientemente la 2-satisfacibilidad problema.

Definición

Como lo definen, por ejemplo, Goldberg y Karzanov (1996) , un grafo simétrico sesgado G es un grafo dirigido, junto con una función σ que mapea los vértices de G con otros vértices de G , que satisface las siguientes propiedades:

1. Para cada vértice v , σ ( v ) ≠ v ,
2. Para cada vértice v , σ (σ ( v )) = v ,
3. Para cada borde ( u , v ), (σ ( v ), σ ( u )) también debe ser un borde.

Uno puede utilizar la tercera propiedad de extender σ a una función de orientación-marcha atrás en los bordes de G .

La gráfica de transposición de G es la gráfica formada al invertir cada borde de G , y σ define un isomorfismo de gráfica de G a su transposición. Sin embargo, en un gráfico de simetría sesgada, se requiere además que el isomorfismo empareje cada vértice con un vértice diferente, en lugar de permitir que un vértice sea mapeado a sí mismo por el isomorfismo o agrupar más de dos vértices en un ciclo de isomorfismo.

Se dice que una trayectoria o ciclo en un gráfico simétrico sesgado es regular si, para cada vértice v de la trayectoria o ciclo, el vértice correspondiente σ ( v ) no es parte de la trayectoria o ciclo.

Ejemplos

Cada gráfico de ruta dirigida con un número par de vértices es simétrico sesgado, a través de una simetría que intercambia los dos extremos de la ruta. Sin embargo, los gráficos de ruta con un número impar de vértices no son simétricos sesgados, porque la simetría de inversión de orientación de estos gráficos mapea el vértice central de la ruta a sí mismo, algo que no está permitido para gráficos simétricos sesgados.

De manera similar, una gráfica de ciclo dirigido es simétrica sesgada si y solo si tiene un número par de vértices. En este caso, el número de asignaciones diferentes σ que realizan la simetría sesgada del gráfico es igual a la mitad de la duración del ciclo.

Gráficos polares / de cambio, gráficos de doble cobertura y gráficos bidireccionales

Un gráfico simétrico sesgado puede definirse de manera equivalente como el gráfico de doble cobertura de un gráfico polar o gráfico de conmutación , ^[1] que es un gráfico no dirigido en el que los bordes incidentes a cada vértice se dividen en dos subconjuntos. Cada vértice del gráfico polar corresponde a dos vértices del gráfico simétrico sesgado y cada borde del gráfico polar corresponde a dos bordes del gráfico simétrico sesgado. Esta equivalencia es la utilizada por Goldberg & Karzanov (1996)para modelar problemas de emparejamiento en términos de gráficos simétricos sesgados; en esa aplicación, los dos subconjuntos de bordes en cada vértice son los bordes no coincidentes y los bordes coincidentes. Zelinka (siguiendo a F. Zitek) y Cook visualizan los vértices de un gráfico polar como puntos donde se unen varias vías de una vía de tren : si un tren entra en un interruptor a través de una vía que viene de una dirección, debe salir por una vía. en la otra dirección. El problema de encontrar curvas suaves que no se intersequen entre puntos dados en una vía de tren surge al probar si ciertos tipos de dibujos de gráficos son válidos. ^[2] y puede modelarse como la búsqueda de una ruta regular en un gráfico simétrico sesgado.

Un concepto estrechamente relacionado es el gráfico bidireccional o gráfico polarizado , ^[3] un gráfico en el que cada uno de los dos extremos de cada borde puede ser una cabeza o una cola, independientemente del otro extremo. Un gráfico bidireccional se puede interpretar como un gráfico polar dejando que la partición de los bordes en cada vértice se determine mediante la partición de los extremos en ese vértice en cabezas y colas; sin embargo, intercambiar los roles de cara y cruz en un solo vértice ("cambiar" el vértice) produce un gráfico bidireccional diferente pero el mismo gráfico polar. ^[4]

Para formar el gráfico de doble cobertura (es decir, el gráfico simétrico sesgado correspondiente) a partir de un gráfico polar G , cree para cada vértice v de G dos vértices v ₀ y v ₁ , y deje σ ( v _i ) =  v _{1 -  i} . Para cada arista e  = ( u , v ) de G , cree dos aristas dirigidas en el gráfico de cobertura, una orientada de u a v y otra orientada de v a u . Si e está en el primer subconjunto de aristas env , estas dos aristas son de u ₀ a v ₀ y de v ₁ a u ₁ , mientras que si e está en el segundo subconjunto, las aristas son de u ₀ a v ₁ y de v ₀ a u ₁ . En la otra dirección, dado un gráfico de simetría sesgada G , se puede formar un gráfico polar que tiene un vértice por cada par de vértices correspondiente en G y un borde no dirigido por cada par de bordes correspondiente en G. 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 polar al que salen y entran.

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

Coincidencia

Al construir emparejamientos en gráficos no dirigidos, es importante encontrar caminos alternos , caminos de vértices que comienzan y terminan en vértices no emparejados, en los que los bordes en posiciones impares en el camino no son parte de un emparejamiento parcial dado y en los que los bordes en Incluso las posiciones en el camino son parte de la correspondencia. Al eliminar los bordes coincidentes de una ruta de este tipo de una coincidencia y agregar los bordes no coincidentes, se puede aumentar el tamaño de la coincidencia. De manera similar, los ciclos que alternan entre bordes emparejados y no emparejados son importantes en los problemas de emparejamiento ponderado. Una ruta o ciclo alterno en un gráfico no dirigido puede modelarse como una ruta o ciclo regular en un gráfico dirigido de simetría sesgada. ^[5] Para crear un gráfico simétrico sesgado a partir de un gráfico no dirigidoG con una M coincidente especificada , vea G como un gráfico de cambio en el que los bordes de cada vértice se dividen en bordes emparejados y no emparejados; una ruta alterna en G es entonces una ruta regular en este gráfico de cambio y un ciclo alterno en G es un ciclo regular en el gráfico de cambio.

Goldberg y Karzanov (1996) generalizaron algoritmos de trayectoria alterna para mostrar que la existencia de una trayectoria regular entre dos vértices cualesquiera de un gráfico simétrico sesgado puede probarse en tiempo lineal. Dada adicionalmente una función de longitud no negativa en los bordes del gráfico que asigna la misma longitud a cualquier borde ey a σ ( e ), la ruta regular más corta que conecta un par dado de nodos en un gráfico de simetría sesgada con m bordes y n vértices se pueden probar en el tiempo O ( m  log  n ). Si se permite que la función de longitud tenga longitudes negativas, la existencia de un ciclo regular negativo puede probarse en tiempo polinomial.

Junto con los problemas de trayectoria que surgen en los emparejamientos, también se han estudiado las generalizaciones asimétricas del teorema de flujo máximo y corte mínimo . ^[6]

Teoría de la naturaleza muerta

Cook (2003) muestra que un patrón de naturaleza muerta en el Juego de la vida de Conway puede dividirse en dos naturalezas muertas más pequeñas si y solo si un gráfico de cambio asociado contiene un ciclo regular. Como muestra, para gráficos de conmutación con un máximo de tres aristas por vértice, esto se puede probar en tiempo polinomial eliminando repetidamente puentes (aristas cuya eliminación desconecta el gráfico) y vértices en los que todas las aristas pertenecen a una sola partición hasta que no haya más. se pueden realizar tales simplificaciones. Si el resultado es un gráfico vacío, no hay un ciclo regular; de lo contrario, se puede encontrar un ciclo regular en cualquier componente sin puente restante. La búsqueda repetida de puentes en este algoritmo se puede realizar de manera eficiente utilizando un algoritmo de gráfico dinámico de Thorup (2000) .

Gabow, Kaplan y Tarjan (1999) consideraron previamente técnicas similares de remoción de puentes en el contexto de emparejamiento .

Satisfacción

Un gráfico de implicaciones . Su simetría sesgada se puede realizar girando el gráfico en un ángulo de 180 grados e invirtiendo todos los bordes.

Una instancia del problema de 2-satisfacibilidad , es decir, una expresión booleana en forma normal conjuntiva con dos variables o negaciones de variables por cláusula, puede transformarse en un gráfico de implicaciones reemplazando cada cláusula.${\displaystyle \scriptstyle u\lor v}$ por las dos implicaciones${\displaystyle \scriptstyle (\lnot u)\Rightarrow v}$ y ${\displaystyle \scriptstyle (\lnot v)\Rightarrow u}$. Este gráfico tiene un vértice para cada variable o variable negada y un borde dirigido para cada implicación; es, por construcción, simétrica sesgada, con una correspondencia σ que asigna cada variable a su negación. Como mostraron Aspvall, Plass y Tarjan (1979) , una asignación satisfactoria a la instancia de 2-satisfacibilidad es equivalente a una partición de este gráfico de implicaciones en dos subconjuntos de vértices, S y σ ( S ), de manera que ningún borde comience en S y termina en σ ( S ). Si existe tal partición, se puede formar una asignación satisfactoria asignando un valor verdadero a cada variable en S y un valor falso a cada variable en σ ( S ). Esto se puede hacer si y solo si noEl componente fuertemente conectado del gráfico contiene tanto algún vértice v como su vértice complementario σ ( v ). Si dos vértices pertenecen al mismo componente fuertemente conectado, las variables correspondientes o variables negadas están restringidas para ser iguales entre sí en cualquier asignación satisfactoria de la instancia de 2-satisfacibilidad. El tiempo total para probar la conectividad fuerte y encontrar una partición del gráfico de implicaciones es lineal en el tamaño de la expresión de 2-CNF dada.

Reconocimiento

Es NP-completo para determinar si un gráfico dirigido dado es simétrico sesgado, por un resultado de Lalonde (1981) que es NP-completo para encontrar una involución de inversión de color en un gráfico bipartito . Tal involución existe si y solo si el gráfico dirigido dado al orientar cada borde de una clase de color a la otra es simétrico sesgado, por lo que probar la simetría sesgada de este gráfico dirigido es difícil. Esta complejidad no afecta a los algoritmos de búsqueda de rutas para gráficos de simetría asimétrica, porque estos algoritmos suponen que la estructura simétrica sesgada se proporciona como parte de la entrada al algoritmo en lugar de requerir que se infiera solo del gráfico.

Notas

1. Los gráficos polares fueron introducidos por Zelinka (1974) y Zelinka (1976a) , y Cook (2003) los denominó gráficos de cambio.
2. Hui, Schaefer y Štefankovič (2004) .
3. Los gráficos bidireccionales fueron introducidos por Edmonds & Johnson (1970) , y Zelinka (1974) y Zelinka (1976a) los denominaron gráficos polarizados .
4. Zaslavsky (1991) , Sección 5; Babenko (2006) .
5. Goldberg y Karzanov (1996) .
6. Goldberg y Karzanov (2004) ; Tutte (1967) .

Referencias

• Aspvall, Bengt; Plass, Michael F .; Tarjan, Robert E. (1979), "Un algoritmo de tiempo lineal para probar la verdad de ciertas fórmulas booleanas cuantificadas", Information Processing Letters , 8 (3): 121-123, doi : 10.1016 / 0020-0190 (79) 90002 -4.
• Babenko, Maxim A. (2006), "Gráficos acíclicos bidireccionales y simétricos sesgados: algoritmos y estructura", Ciencias de la computación - Teoría y aplicaciones , Lecture Notes in Computer Science, 3967 , Springer-Verlag, págs. 23–34, arXiv : matemáticas / 0607547 , doi : 10.1007 / 11753728_6 , ISBN 978-3-540-34166-6.
• Biggs, Norman (1974), Teoría de grafos algebraicos , Londres: Cambridge University Press.
• Cook, Matthew (2003), "Teoría de la naturaleza muerta", Nuevas construcciones en autómatas celulares , Estudios del Instituto Santa Fe en las ciencias de la complejidad, Oxford University Press, págs. 93-118.
• Edmonds, Jack ; Johnson, Ellis L. (1970), "Emparejamiento: una clase bien resuelta de programas lineales", Estructuras combinatorias y sus aplicaciones: Actas del Simposio de Calgary, junio de 1969 , Nueva York: Gordon y Breach. 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 .
• Gabow, Harold N .; Kaplan, Haim; Tarjan, Robert E. (1999), "Algoritmos únicos de coincidencia máxima", Proc. 31st ACM Symp. Teoría de la Computación (STOC) , págs. 70–78, doi : 10.1145 / 301250.301273 , ISBN 1-58113-067-8.
• Goldberg, Andrew V .; Karzanov, Alexander V. (1996), "Problemas de trayectoria en gráficas simétricas sesgadas", Combinatorica , 16 (3): 353–382, doi : 10.1007 / BF01261321.
• Goldberg, Andrew V .; Karzanov, Alexander V. (2004), "Flujos y emparejamientos asimétricos máximos", Programación matemática , 100 (3): 537–568, arXiv : math / 0304290 , doi : 10.1007 / s10107-004-0505-z.
• Hui, Peter; Schaefer, Marcus; Štefankovič, Daniel (2004), "Vías de tren y dibujos confluentes", Proc. 12th Int. Symp. Dibujo de gráficos , Notas de clase en Ciencias de la Computación, 3383 , Springer-Verlag, págs. 318–328.
• Lalonde, François (1981), "Le problème d'étoiles pour graphes est NP-complet", Discrete Mathematics , 33 (3): 271–280, doi : 10.1016 / 0012-365X (81) 90271-5 , MR  0602044.
• Thorup, Mikkel (2000), "Conectividad gráfica totalmente dinámica casi óptima", Proc. 32º Simposio ACM sobre Teoría de la Computación , págs. 343–350, doi : 10.1145 / 335305.335345 , ISBN 1-58113-184-4.
• Tutte, WT (1967), "Dígrafos antisimétricos", Canadian Journal of Mathematics , 19 : 1101-1117, doi : 10.4153 / CJM-1967-101-8.
• Zaslavsky, Thomas (1982), "Gráficos firmados", Matemáticas aplicadas discretas , 4 : 47–74, doi : 10.1016 / 0166-218X (82) 90033-6 , hdl : 10338.dmlcz / 127957.
• Zaslavsky, Thomas (1991), "Orientación de gráficos con signo", European Journal of Combinatorics , 12 (4): 361–375, doi : 10.1016 / s0195-6698 (13) 80118-7.
• Zelinka, Bohdan (1974), "Gráficos polares y tráfico ferroviario", Aplikace Matematiky , 19 : 169-176.
• Zelinka, Bohdan (1976a), "Isomorfismos de gráficos polares y polarizados", Checoslovak Mathematical Journal , 26 : 339–351.
• Zelinka, Bohdan (1976b), "Analoga del teorema de Menger para gráficos polares y polarizados", Checoslovaco Mathematical Journal , 26 : 352–360.