Talk:Max-flow min-cut theorem

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

High

This article has been rated as High-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Split page to Min-cut max-flow and Maximum flow problem

I propose pulling out the definition of the max flow problem as part of a separate page on the maximum flow problem. The new page might be structured like so:

Definition
Related problems, reductions from:
- multiple source/sinks
- maximum bipartite graph matching)
Methods for solving
- Ford-Fulkerson
- Push-relabel (aka preflow relabel)

The max flow min cut theorem is certainly central to proving the correctness of both methods.

Thoughts? Comments? Cries of dismay? --NikolasCo 06:38, 22 December 2005 (UTC)[reply]

Ooops! I am very sorry. I did not read this talk page before rewriting the article. Comments: Need methods for solving be listed here? Shouldn't they be in Maximum flow problem? Shouldn't also stuff about problems related to max flow, such as bipartite matching, be there? When you write multiple sources/sinks, do you mean a multi-commodity problem (only known polynomic solution is linear programming, or do you mean a problem where you can add a super-source and a super-sink, and solve with regular max flow? --- Nils Grimsmo 07:55, 10 January 2006 (UTC)[reply]

It's okay. You did most of what I outlined and had in mind anyway :) Note that I said "the new page might be structured like so," I intended for Maximum flow problem to be laid out the way it is now. Re: multiple sources/sinks: I was thinking of the simple super-source and super-sink. I agree that multicommodity flow problem should be a separate page.

Should it be multi-commodity flow with a hyphen or without? I am not an English expert, so I am not sure. In my native language (Norwegian) we don't use a hypen when concatenating words, but I think you do in English. Is this a special case because the word multi describes the word commodity? In Cormen et al. they write multicommodity flow without a hyphen. On NIST:DADS they write it with a hyphen. If I enter "multi-commodity" in Google, I get a 'Did you mean: "multicommodity"' spelling suggestion, even though the two spellings have approximately the same number of hits. Cormen et al. also write max-flow min-cut theorem with hyphens. Should this article be renamed to that? Again, I am not sure which is more correct, but I like it better with hyphens, as it shows which of the words "belong" toghether. -- Nils Grimsmo 14:26, 13 January 2006 (UTC)[reply]

Number of cuts

Why is the number of cuts $2^{|V|-1}-1\,$ , and not $2^{|V|-2}\,$ , as the article previously said? For $|V|=3\,$ , there is one node $u\,$ apart from $s\,$ and $t\,$ . There are two different cuts, one with $u\in S$ and one with $u\in T$ . But $2^{|V|-1}-1=2^{3-1}-1=3\,$ . I think perhaps the editor did not read that $s\in S$ and $t\in T$ was fixed? Klem fra Nils Grimsmo 07:55, 30 March 2007 (UTC)[reply]

I'm also quite confused by the reported number of cuts. Shouldn't the correct number be $(|V|-1)(|V|-2)/2$ ? I have no idea where the whole $2^{|V|-2}$ comes from. The reasoning for this is that we are looking at the amount of ways the set can be partitioned (excluding source and sink) into 2 disjoint sets. This is the same thing as counting |V|-1 choose 2. —Preceding unsigned comment added by 66.188.12.43 (talk) 13:15, 2 August 2008 (UTC)[reply]

Menger

The article says "derived from Menger's theorem" - aren't there proofs that don't depend on Menger?

Visualization

I'm trying to make an image to capture the liquid-flowing-through-pipes concept.

Not entirely happy with it, but I think it's a start. ~ Booya ^Bazooka 23:39, 24 October 2008 (UTC)[reply]

I'm reluctant to call anything generated by my beloved Graphviz "old and busted", but I like the new hotness --- you don't see a lot of color in CS articles. It might be nice to do something to indicate that s and t are the source and sink, but I think this should definitely go in... --mgreenbe (talk) 16:28, 27 October 2008 (UTC)[reply]

Generalized Max-Flow Min-Cut Theorem

This "generalized max-flow min-cut theorem" is a trivial corollary of the max-flow min-cut theorem. It is not a generalization at all! It should be deleted. —Preceding unsigned comment added by 71.102.227.211 (talk) 06:26, 9 December 2009 (UTC)[reply]

Linear programming formulation

I don't understand the 'min cut'-side of the linear programming formulation: how are these numbers p_i defined? Where do the d_{ij} come from? Could someone extend this part of the article?

(Also: the inequallity out-flow minus in-flow at vertex i is non-negative in the LP-formulation of 'max flow' seems odd: shouldn't that be an equallity instead of an inequallity? — Preceding unsigned comment added by Octonion (talk • contribs) 18:53, 30 January 2011 (UTC)[reply]

There seems to be one constraint missing in the max-flow Linear program, viz., the flow conservation at t. —Preceding unsigned comment added by 67.176.193.78 (talk) 03:29, 18 March 2011 (UTC)[reply]

$\nabla _{t}$ needs to be defined somewhere.Wikihelperhelper (talk) 21:00, 8 August 2011 (UTC)[reply]

I think that either $\nabla _{t}$ there is $\nabla _{s}$ - wich makes some sort of sense - or $\nabla _{v}$ means the flow's value "through vertex v", wich is the maximum of the sum of the flow values on every incoming edge and the sum of the flow values on every outgoing edge. Netom (talk) 22:10, 4 February 2013 (UTC)[reply]

Presented Min cut formulation is different in the pdf file given as a reference. — Preceding unsigned comment added by 47.218.196.215 (talk) 23:43, 8 May 2020 (UTC)[reply]

Flows - mistake ?

"The value of a flow is defined by

|f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},

where as above $s$ is the source node and $t$ is the sink node. In the fluid analogy, it represents the amount of fluid entering the network at the source node, *minus* the amount of flow leaving the network at the sink node."

Isn't "minus" wrong here? Actually IN flow minus OUT flow should always be zero (given the aforementioned!). - Anonymous, 2018-10-24

I think you are right, I fixed it. --Erel Segal (talk) 13:27, 17 January 2019 (UTC)[reply]

vital article -- really?

This is currently marked as a "vital article" but I find that rather incredible. Out of the 22K articles we have in mathematics, I find it unbelievable that this could ever rise above a rating of "mid priority" (even that seems a stretch) and ascend to the ranks of "vital". 67.198.37.16 (talk) 16:07, 6 June 2021 (UTC)[reply]