En teoría de grafos , una rama de las matemáticas, un grafo antisimétrico es un grafo dirigido que es isomorfo a su propio grafo transpuesto , el grafo formado al invertir todas sus aristas, bajo un isomorfismo que es una involución sin ningún punto fijo . Los grafos antisimétricos son idénticos a los grafos de doble recubrimiento de los grafos bidireccionales .
Los grafos antisimétricos fueron introducidos por primera vez bajo el nombre de dígrafos antisimétricos por Tutte (1967), más tarde como grafos de doble recubrimiento de grafos polares por Zelinka (1976b), y aún más tarde como grafos de doble recubrimiento de grafos bidireccionales por Zaslavsky (1991). Surgen al modelar la búsqueda de caminos alternativos y ciclos alternativos en algoritmos para encontrar coincidencias en grafos, 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 grafos y en los grafos de implicación utilizados para resolver eficientemente el problema de 2-satisfacibilidad .
Como lo definen, por ejemplo, Goldberg y Karzanov (1996), un grafo antisimétrico G es un grafo dirigido, junto con una función σ que asigna vértices de G a otros vértices de G , y que satisface las siguientes propiedades:
Se puede utilizar la tercera propiedad para extender σ a una función de inversión de orientación en los bordes de G.
El grafo transpuesto de G es el grafo formado al invertir cada arista de G y σ define un isomorfismo de grafo desde G hasta su transpuesta. Sin embargo, en un grafo antisimétrico, se requiere además que el isomorfismo empareje cada vértice con un vértice diferente, en lugar de permitir que un vértice se mapee a sí mismo por el isomorfismo o que se agrupen más de dos vértices en un ciclo de isomorfismo.
Se dice que un camino o ciclo en un gráfico antisimétrico es regular si, para cada vértice v del camino o ciclo, el vértice correspondiente σ( v ) no es parte del camino o ciclo.
Todo grafo de trayectoria dirigida con un número par de vértices es antisimétrico, mediante una simetría que intercambia los dos extremos de la trayectoria. Sin embargo, los grafos de trayectoria con un número impar de vértices no son antisimétricos, porque la simetría de inversión de orientación de estos grafos asigna el vértice central de la trayectoria a sí mismo, algo que no está permitido para los grafos antisimétricos.
De manera similar, un grafo de ciclo dirigido es antisimétrico si y solo si tiene un número par de vértices. En este caso, el número de aplicaciones diferentes σ que realizan la simetría antisimétrica del grafo es igual a la mitad de la longitud del ciclo.
Un grafo antisimétrico puede definirse de manera equivalente como el grafo de doble recubrimiento de un grafo polar o grafo de cambio , [1] que es un grafo no dirigido en el que las aristas incidentes a cada vértice están divididas en dos subconjuntos. Cada vértice del grafo polar corresponde a dos vértices del grafo antisimétrico, y cada arista del grafo polar corresponde a dos aristas del grafo antisimétrico. Esta equivalencia es la utilizada por Goldberg y Karzanov (1996) para modelar problemas de emparejamiento en términos de grafos antisimétricos; en esa aplicación, los dos subconjuntos de aristas en cada vértice son las aristas no emparejadas y las aristas emparejadas. Zelinka (siguiendo a F. Zitek) y Cook visualizan los vértices de un grafo polar como puntos donde se juntan múltiples vías de una vía de tren : si un tren entra en un cambio a través de una vía que viene de una dirección, debe salir a través de una vía en la otra dirección. El problema de encontrar curvas suaves que no se intersequen entre sí 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 trayectoria regular en un gráfico antisimétrico.
Un concepto estrechamente relacionado es el de grafo bidireccional o grafo polarizado , [3] un grafo en el que cada uno de los dos extremos de cada arista puede ser una cara o una cola, independientemente del otro extremo. Un grafo bidireccional puede interpretarse como un grafo 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 caras y colas en un solo vértice ("cambiar" el vértice) produce un grafo bidireccional diferente pero el mismo grafo polar. [4]
Para formar el grafo de doble recubrimiento (es decir, el grafo antisimétrico correspondiente) a partir de un grafo 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 arista e = ( u , v ) de G , cree dos aristas dirigidas en el grafo de recubrimiento, una orientada de u a v y una orientada 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 a u 1 . En la otra dirección, dado un grafo antisimétrico G , se puede formar un grafo polar que tenga un vértice para cada par correspondiente de vértices en G y una arista no dirigida para cada par correspondiente de aristas en G . Los bordes no dirigidos en cada vértice del gráfico polar se pueden dividir en dos subconjuntos según de qué vértice del gráfico polar salen y al que llegan.
Una ruta o ciclo regular de un gráfico antisimé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 emparejamientos en grafos 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 posiciones pares en el camino son parte del emparejamiento. Al eliminar los bordes emparejados de dicho camino de un emparejamiento y agregar los bordes no emparejados, se puede aumentar el tamaño del emparejamiento. De manera similar, los ciclos que alternan entre bordes emparejados y no emparejados son importantes en problemas de emparejamiento ponderado. Un camino o ciclo alternante en un grafo no dirigido se puede modelar como un camino o ciclo regular en un grafo dirigido antisimétrico. [5] Para crear un grafo antisimétrico a partir de un grafo no dirigido G con un emparejamiento especificado M , vea G como un grafo conmutador en el que los bordes en cada vértice se dividen en bordes emparejados y no emparejados; un camino alterno en G es entonces un camino regular en este gráfico de conmutación y un ciclo alterno en G es un ciclo regular en el gráfico de conmutación.
Goldberg y Karzanov (1996) generalizaron algoritmos de trayectorias alternas para demostrar que la existencia de una trayectoria regular entre dos vértices cualesquiera de un grafo antisimétrico puede probarse en tiempo lineal. Dada además una función de longitud no negativa en los bordes del grafo que asigna la misma longitud a cualquier borde e y a σ( e ), la trayectoria regular más corta que conecta un par dado de nodos en un grafo antisimétrico con m bordes y n vértices puede probarse en 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 generalizaciones antisimétricas del teorema de flujo máximo y corte mínimo . [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 solo si un gráfico de conmutación asociado contiene un ciclo regular. Como muestra, para gráficos de conmutación con como máximo tres aristas por vértice, esto puede probarse 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 única partición hasta que no se puedan realizar más simplificaciones de este tipo. 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 restante sin puentes. La búsqueda repetida de puentes en este algoritmo puede realizarse 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.
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 implicación 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, antisimétrico, con una correspondencia σ que asigna cada variable a su negación. Como Aspvall, Plass y Tarjan (1979) demostraron, una asignación satisfactoria a la instancia de 2-satisfacibilidad es equivalente a una partición de este gráfico de implicación en dos subconjuntos de vértices, S y σ( S ), de modo que ninguna arista comience en S y termine 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 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 las variables negadas están restringidas a 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 implicación es lineal en el tamaño de la expresión 2-CNF dada.
Es NP-completo determinar si un grafo dirigido dado es antisimétrico, por un resultado de Lalonde (1981) de que es NP-completo encontrar una involución de inversión de color en un grafo bipartito . Tal involución existe si y solo si el grafo dirigido dado al orientar cada borde de una clase de color a la otra es antisimétrico, por lo que probar la antisimetría de este grafo dirigido es difícil. Esta complejidad no afecta a los algoritmos de búsqueda de caminos para grafos antisimétricos, porque estos algoritmos suponen que la estructura antisimétrica se da como parte de la entrada al algoritmo en lugar de requerir que se infiera solo del grafo.
