Lesson plan

Dijoin

, the resulting graph becomes strongly connected. This means that each of these is a dijoin. In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, includes at least one edge contained in the dicut. Here, a dicut is a set of edges in a directed graph, defined from a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Woodall's conjecture, an unsolved problem in this area, states that in any directed graph the minimum number of edges in a dicut (the unweighted minimum closure) equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins). A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver. The Lucchesi–Younger theorem states that the minimum size of a dijoin, in any given directed graph, equals the maximum number of disjoint dicuts that can be found in the graph. The minimum weight dijoin in a weighted graph can be found in polynomial time, and is a special case of the submodular flow problem. In planar graphs, dijoins and feedback arc sets are dual concepts.…

Back to article

Article summary

, the resulting graph becomes strongly connected. This means that each of these is a dijoin. In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, includes at least one edge contained in the dicut. Here, a dicut is a set of edges in a directed graph, defined from a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Woodall's conjecture, an unsolved problem in this area, states that in any directed graph the minimum number of edges in a dicut (the unweighted minimum closure) equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins). A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver. The Lucchesi–Younger theorem states that the minimum size of a dijoin, in any given directed graph, equals the maximum number of disjoint dicuts that can be found in the graph. The minimum weight dijoin in a weighted graph can be found in polynomial time, and is a special case of the submodular flow problem. In planar graphs, dijoins and feedback arc sets are dual concepts.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.