La conjetura de Woodall

En las matemáticas de los grafos dirigidos , la conjetura de Woodall es una relación no probada entre dicuts y dijoins . Fue planteada por Douglas Woodall en 1976. ^{[ 1 ]}

En un grafo dirigido, un dicut es un conjunto de aristas definido a partir de una partición de los vértices en dos subconjuntos, de modo que todas las aristas que cruzan la partición lo hacen en la misma dirección. Un dijoin es un subconjunto de aristas que, al contraerse, produce un grafo fuertemente conexo ; equivalentemente, es un subconjunto de aristas que incluye al menos una arista de cada dicut. ^{[ 2 ]}

Según el teorema de Lucchesi-Younger , si el número mínimo de aristas en un dicut es${\displaystyle k}$, entonces puede haber como máximo${\displaystyle k}$Dijoins disjuntos en el grafo, porque cada uno debe incluir una arista diferente del dicut más pequeño. La conjetura de Woodall afirma que, en este caso, siempre es posible encontrar${\displaystyle k}$Dijoins disjuntos. Es decir, cualquier grafo dirigido en el que el número mínimo de aristas en un dicut es igual al número máximo de dijoins disjuntos que se pueden encontrar en el grafo (un empaquetamiento de dijoins). ^{[ 2 ] [ 1 ]}

Es un resultado popular que el teorema es cierto para grafos dirigidos cuyo corte mínimo tiene dos aristas. ^{[ 2 ]} Cualquier instancia del problema puede reducirse a un grafo dirigido acíclico tomando la condensación de la instancia, un grafo formado al contraer cada componente fuertemente conexa a un solo vértice. Otra clase de grafos para los que se ha demostrado la veracidad del teorema son los grafos dirigidos acíclicos en los que cada vértice fuente (un vértice sin aristas entrantes) tiene un camino a cada vértice sumidero (un vértice sin aristas salientes). ^{[ 3 ] [ 4 ]}

En cada gráfico cuyo tamaño mínimo de corte es${\displaystyle k}$, existen al menos${\displaystyle \lfloor k/6\rfloor }$Dijoins disjuntos. Si una conjetura de WT Tutte sobre la existencia de 5-flujos sin cero en ningún lugar en grafos biconectados no dirigidos es cierta, esta cota mejoraría a${\displaystyle \lfloor k/5\rfloor }$. ^{[ 5 ]}

Una versión ponderada fraccionaria de la conjetura, planteada por Jack Edmonds y Rick Giles, fue refutada por Alexander Schrijver . ^{[ 6 ] [ 7 ] [ 2 ]} En la otra dirección, el teorema de Lucchesi-Younger establece 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. ^{[ 8 ] [ 9 ]}

• Feofiloff, Paulo (30 de noviembre de 2005), La conjetura de Woodall sobre el envasado de Dijon: una revisión (PDF)
• "La conjetura de Woodall" , Open Problem Garden , 5 de abril de 2007