En teoría de grafos , una rama de las matemáticas, un gráfico sesgado-simétrico es un gráfico dirigido que es isomorfo a su propio gráfico transpuesto , el gráfico formado al invertir todas sus aristas, bajo un isomorfismo que es una involución sin puntos fijos . Los gráficos sesgados-simétricos son idénticos a los gráficos de doble cobertura de los gráficos bidireccionales .
Los gráficos sesgados-simétricos fueron introducidos por primera vez bajo el nombre de dígrafos antisimétricos por Tutte (1967), más tarde como gráficos de doble cobertura de gráficos polares por Zelinka (1976b), y aún más tarde como gráficos de doble cobertura de 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 implicaciones utilizados para resolver eficientemente el problema de 2-satisfacibilidad .
Como lo definen, por ejemplo, Goldberg y Karzanov (1996), un gráfico asimétrico G es un gráfico dirigido, junto con una función σ que asigna vértices de G a otros vértices de G , satisfaciendo las siguientes propiedades:
Se puede usar la tercera propiedad para extender σ a una función de inversión de orientación en los bordes de G.
La gráfica transpuesta de G es la gráfica formada al invertir cada arista de G , y σ define un isomorfismo gráfico de G a su transpuesta. Sin embargo, en un gráfico simétrico sesgado, se requiere adicionalmente que el isomorfismo empareje cada vértice con un vértice diferente, en lugar de permitir que el isomorfismo asigne un vértice a sí mismo o agrupe más de dos vértices en un ciclo de isomorfismo.
Se dice que una ruta o ciclo en un gráfico asimétrico es regular si, para cada vértice v de la ruta o ciclo, el vértice correspondiente σ ( v ) no es parte de la ruta o ciclo.
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 asigna el vértice central del camino a sí mismo, algo que no está permitido para los gráficos simétricos sesgados.
De manera similar, un gráfico de ciclo dirigido es asimétrico 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.
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 cambio , [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 y Karzanov (1996) para modelar problemas de emparejamiento en términos de gráficos asimétricos; en esa aplicación, los dos subconjuntos de aristas en cada vértice son las aristas no coincidentes y las aristas 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 desvío por 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 de una vía de tren surge al probar si ciertos tipos de dibujos 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 de gráfico bidireccional o gráfico polarizado , [3] un gráfico en el que cada uno de los dos extremos de cada arista puede ser una cabeza o una cola, independientemente del otro extremo. Un gráfico bidireccional puede interpretarse como un gráfico polar dejando que la partición de las aristas en cada vértice esté determinada por la partición de los puntos finales en ese vértice en caras 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 0 y v 1 , y sea σ( v i ) = v 1 − i . Para cada borde e = ( u , v ) de G , cree dos bordes dirigidos en el gráfico de cobertura, uno orientado de u a v y otro orientado de v a u . Si e está en el primer subconjunto de aristas en v , estas dos aristas son de u 0 a v 0 y de v 1 a u 1 , mientras que si e está en el segundo subconjunto, las aristas son de u 0 a v 1 y de v 0 en u 1 . En la otra dirección, dado un gráfico asimétrico G , se puede formar un gráfico polar que tenga un vértice por cada par de vértices correspondiente en G y una arista no dirigida por cada par de aristas 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 del que salen y al que entran.
Una ruta o ciclo regular de un gráfico sesgado-simétrico 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.
Al construir coincidencias en gráficos no dirigidos, es importante encontrar caminos alternos , caminos de vértices que comienzan y terminan en vértices no coincidentes, en los que los bordes en posiciones impares en el camino no son parte de una coincidencia parcial dada y en los que los bordes en incluso las posiciones en el camino son parte del emparejamiento. Al eliminar los bordes coincidentes de dicha ruta 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 aristas coincidentes y no coincidentes son importantes en los problemas de coincidencia ponderada. Una ruta o ciclo alterno en un gráfico no dirigido se puede modelar como una ruta o ciclo regular en un gráfico dirigido con simetría sesgada. [5] Para crear un gráfico simétrico sesgado a partir de un gráfico no dirigido G con una M coincidente especificada , vea G como un gráfico de cambio en el que los bordes en cada vértice se dividen en bordes coincidentes y no coincidentes; 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 caminos alternos para mostrar que la existencia de un camino regular entre dos vértices cualesquiera de un gráfico sesgado-simétrico se puede probar en tiempo lineal. Dada además una función de longitud no negativa en los bordes del gráfico que asigna la misma longitud a cualquier borde e y a σ ( e ), el camino regular más corto que conecta un par de nodos dado en un gráfico simétrico sesgado con m bordes y Se pueden probar n vértices 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 se puede probar en tiempo polinómico.
Junto con los problemas de trayectoria que surgen en los emparejamientos, también se han estudiado generalizaciones asimétricas del teorema de corte mínimo de flujo máximo . [6]
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 sólo si un gráfico de cambio asociado contiene un ciclo regular. Como muestra, para gráficos de cambio con como máximo 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 todos los bordes pertenecen a una única partición hasta que no haya más Se pueden realizar tales simplificaciones. Si el resultado es un gráfico vacío , no existe un ciclo regular; de lo contrario, se puede encontrar un ciclo regular en cualquier componente restante sin puente. 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 eliminación de puentes en el contexto del emparejamiento.
Un ejemplo 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, se puede transformar en un gráfico de implicaciones reemplazando cada cláusula por las dos implicaciones y . Este gráfico tiene un vértice para cada variable o variable negada, y una arista dirigida para cada implicación; es, por construcción, sesgado-simétrico, con una correspondencia σ que asigna cada variable a su negación. Como demostraron 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 modo que ninguna arista 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 ningún componente fuertemente conectado del gráfico contiene algún vértice v y su vértice complementario σ ( v ). Si dos vértices pertenecen al mismo componente fuertemente conectado, las variables correspondientes o las variables negadas están obligadas a ser iguales entre sí en cualquier asignación satisfactoria de la instancia de 2-satisfacibilidad. El tiempo total para probar una conectividad fuerte y encontrar una partición del gráfico de implicaciones es lineal en el tamaño de la expresión 2-CNF dada.
Es NP-completo determinar si un gráfico dirigido dado es asimétrico, según un resultado de Lalonde (1981) de que es NP-completo encontrar una involución con inversión de color en un gráfico bipartito . Tal involución existe si y sólo si el gráfico dirigido obtenido al orientar cada borde de una clase de color a la otra es asimétrico, por lo que probar la simetría asimétrica de este gráfico dirigido es difícil. Esta complejidad no afecta a los algoritmos de búsqueda de rutas para gráficos simétricos asimétricos, 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 a partir del gráfico.
