En matemáticas, un dijoin es un subconjunto de las aristas de un grafo dirigido , con la propiedad de que contraer cada arista en el dijoin produce un grafo fuertemente conexo . De manera equivalente, un dijoin es un subconjunto de las aristas que, para cada dicut , incluye al menos una arista que cruza el dicut. Aquí, un dicut es una partición de los vértices en dos subconjuntos, de modo que cada arista que tiene un punto final en ambos subconjuntos está dirigida desde el primer subconjunto al segundo.
La conjetura de Woodall , un problema no resuelto en esta área, establece que en cualquier grafo dirigido el número mínimo de aristas en un dicut (el cierre mínimo no ponderado) es igual al número máximo de dijoins disjuntos que se pueden encontrar en el grafo (un empaquetamiento de dijoins). [1] [2] Una versión ponderada fraccionaria de la conjetura, planteada por Jack Edmonds y Rick Giles, fue refutada por Alexander Schrijver . [3] [4] [1]
El teorema de Lucchesi-Younger establece que el tamaño mínimo de un dijoin, en cualquier grafo dirigido dado, es igual al número máximo de dicuts disjuntos que se pueden encontrar en el grafo. [5] [6] El dijoin de peso mínimo en un grafo ponderado se puede encontrar en tiempo polinomial , [7] y es un caso especial del problema de flujo submodular . [8]
En los grafos planares , los dijoins y los conjuntos de arcos de retroalimentación son conceptos duales. El grafo dual de un grafo dirigido, incrustado en el plano, es un grafo con un vértice para cada cara del grafo dado, y una arista dual entre dos vértices duales cuando las dos caras correspondientes están separadas por una arista. Cada arista dual cruza una de las aristas del grafo original, girada 90° en el sentido de las agujas del reloj. Un conjunto de arcos de retroalimentación es un subconjunto de las aristas que incluye al menos una arista de cada ciclo dirigido. Para un dijoin en el grafo dado, el conjunto correspondiente de aristas forma un corte dirigido en el grafo dual, y viceversa. [9] Esta relación entre estos dos problemas permite que el problema del conjunto de arcos de retroalimentación se resuelva de manera eficiente para grafos planares, aunque es NP-hard para otros tipos de grafos. [7]