To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Lucchesi–Younger theorem

From Wikipedia, the free encyclopedia

In the mathematics of directed graphs, the Lucchesi–Younger theorem is a relationship between dicuts and dijoins. It was published by Cláudio L. Lucchesi and Daniel H. Younger in 1978.[1][2] Their proof resolved a conjecture that had been posed roughly a decade earlier by Younger,[3] and in unpublished work by Neil Robertson,[2] motivated by the duality in planar graphs between dijoins and feedback arc sets.[2][4]

A dicut is a partition of the vertices into two subsets such that all edges that cross the partition do so in the same direction. A dijoin is a subset of edges that, when contracted, produces a strongly connected graph; equivalently, it is a subset of edges that includes at least one edge from each dicut.[5]

If a collection of dicuts are all disjoint, any dijoin must have at least one edge from each of these dicuts, and must have size at least equal to the size of the collection. Therefore, the maximum number of disjoint dicuts in any graph must be less than or equal to the minimum size of a dijoin. The Lucchesi–Younger theorem states that this relation is always an equality. The minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.[1][2]

References

  1. ^ a b 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
  2. ^ a b c d 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
  3. ^ Younger, D. H. (1969), "Maximum families of disjoint directed cut sets", Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, pp. 329–333, MR 0258678
  4. ^ Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365
  5. ^ Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392
This page was last edited on 25 October 2023, at 00:37
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.