Max-flow min-cut: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
== Max-flow min-cut theorem == | == Max-flow min-cut theorem == | ||
Let <math>G=(V,A)</math>, <math>s,t\in V</math>, and for <math>a\in A</math> let <math><math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> and <math>f</math> is an <math>(s,t)<math>-flow. Then the following three statements are equivalent: | Let <math>G=(V,A)</math>, <math>s,t\in V</math>, and for <math>a\in A</math> let <math><math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math> and <math>f</math> is an <math>(s,t)</math>-flow. Then the following three statements are equivalent: | ||
# <math>f</math> is maximum. | |||
# There is a [[Basic flow definitions#Cuts and saturated cuts|saturated cut]]. | |||
# There is no [[Basic flow definitions#Flow augmenting path|flow-augmenting path]]. | |||
Revision as of 19:18, 19 October 2014
Max-flow min-cut theorem
Let [math]\displaystyle{ G=(V,A) }[/math], [math]\displaystyle{ s,t\in V }[/math], and for [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ \lt math\gt u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math] and [math]\displaystyle{ f }[/math] is an [math]\displaystyle{ (s,t) }[/math]-flow. Then the following three statements are equivalent:
- [math]\displaystyle{ f }[/math] is maximum.
- There is a saturated cut.
- There is no flow-augmenting path.
is a saturated cut if, and only if, there is no augmenting -path.
Proof: First suppose there is no augmenting -path. Let denote the set of all nodes such that there is an augmenting -path. Obviously, the cut is saturated. Second, suppose there is an augmenting -path . Consider an arbitrary, yet fixed -cut . Since the first node of is in and the last node of is in , there must be at least one arc of from a node in to a node in . As is augmenting, cannot be saturated. Known Related Topics Known Related Topics Remark Remark Reference Reference The current flow is maximum if, and only if, there is a saturated -cut.
Proof: First, suppose there is no saturated -cut. Above it was shown that, then, there is an augmenting . Augmenting the current flow along this path would increase the total flow value by at least one unit. Therefore, the current flow is not maximum. Second, suppose the current flow is not maximum. Then there is a flow whose total flow value is higher than that of . Let be an arbitrary, yet fixed -cut. Since the total flow value of an -flow equals the total flow over any -cut, sends more flow than over . In particular, at least one arc from to must send more flow of than of if points from to , or less flow of than of if points from to . In either case, is not saturated.