Dicut

En matemáticas, un dicut es un conjunto de aristas en un grafo dirigido , definido a partir de una partición de los vértices en dos subconjuntos, de modo que cada arista que tiene un extremo en ambos subconjuntos está dirigida del primer subconjunto al segundo. Esto es análogo a un corte en grafos no dirigidos (aunque el corte se refiere a la partición de vértices en lugar del conjunto de aristas entre ellos, por lo que es más preciso decir que el dicut es análogo al conjunto de corte ). Cada componente fuertemente conexa del grafo debe estar completamente contenida en uno de los dos subconjuntos, por lo que un grafo fuertemente conexo no tiene dicuts no triviales. ^{[ 1 ]} A menudo, se supone que el grafo dirigido subyacente es débilmente conexo ; de lo contrario, el conjunto de aristas vacío correspondería a múltiples particiones de vértices.

El segundo de los dos subconjuntos en un dicut, un subconjunto de vértices sin aristas que salgan del subconjunto, se llama cierre. El problema del cierre es el problema algorítmico de encontrar un dicut, en un grafo dirigido ponderado por aristas, cuyo peso total sea lo más grande posible. Se puede resolver en tiempo polinomial . ^{[ 2 ]}

En los grafos planares débilmente conexos , los dicuts y los ciclos son conceptos duales. El grafo dual de un grafo dirigido, incrustado en el plano, es un grafo con un vértice por 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 sentido horario. Para un dicut en el grafo dado, los duales de las aristas en el dicut forman un ciclo dirigido en el grafo dual, y viceversa. ^{[ 3 ]}

Un dijoin se puede definir como un conjunto de aristas que contiene al menos una arista de cada dicut; para que esto exista, el grafo dirigido dado debe ser débilmente conexo. Cuando las aristas de un dijoin se contraen, el resultado es un grafo fuertemente conexo. La conjetura de Woodall , un problema sin resolver en esta área, afirma 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 ] [ 4 ]} Una versión ponderada fraccionaria de la conjetura, planteada por Jack Edmonds y Rick Giles, fue refutada por Alexander Schrijver . ^{[ 5 ] [ 6 ] [ 1 ]} En la otra dirección, el teorema de Lucchesi-Younger afirma que el tamaño mínimo de un dijoin es igual al número máximo de dicuts disjuntos que se pueden encontrar en un grafo dado. ^{[ 7 ] [ 8 ]}