Dicut
In mathematics, a dicut is a partition of the vertices of a directed graph into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Each strongly connected component of the graph must be entirely contained in one of the two subsets, so a strongly connected graph has no nontrivial dicuts.[1]
The second of the two subsets in a dicut, a subset of vertices with no edges that exit the subset, is called a closure. The closure problem is the algorithmic problem of finding a dicut, in an edge-weighted directed graph, whose total weight is as large as possible. It can be solved in polynomial time.[2]
In planar graphs, dicuts and cycles are dual concepts. The dual graph of a directed graph, embedded in the plane, is a graph with a vertex for each face of the given graph, and a dual edge between two dual vertices when the corresponding two faces are separated by an edge. Each dual edge crosses one of the original graph edges, turned by 90° clockwise. For a dicut in the given graph, the duals of the edges that cross the dicut form a directed cycle in the dual graph, and vice versa.[3]
A dijoin can be defined as a set of edges that crosses all dicuts; when the edges of a dijoin are contracted, the result is a strongly connected graph. 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).[1][4] A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver.[5][6][1] In the other direction, the Lucchesi–Younger theorem states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.[7][8]
References
[edit]- ^ a b c Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392
- ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "19.2 Maximum weight closure of a graph", Network flows, Englewood Cliffs, NJ: Prentice Hall Inc., pp. 719–724, ISBN 0-13-617549-X, MR 1205775.
- ^ Noy, Marc (2001), "Acyclic and totally cyclic orientations in planar graphs", American Mathematical Monthly, 108 (1): 66–68, doi:10.2307/2695680, JSTOR 2695680, MR 1857074.
- ^ Woodall, D. R. (1978), "Menger and König systems", in Alavi, Yousef; Lick, Don R. (eds.), Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, vol. 642, Berlin: Springer, pp. 620–635, doi:10.1007/BFb0070416, MR 0499529
- ^ Edmonds, Jack; Giles, Rick (1977), "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, pp. 185–204, MR 0460169
- ^ Schrijver, A. (1980), "A counterexample to a conjecture of Edmonds and Giles", Discrete Mathematics, 32 (2): 213–215, doi:10.1016/0012-365X(80)90057-6, MR 0592858
- ^ Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi:10.1016/0095-8956(76)90049-6, MR 0427138
- ^ Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR 0500618