Max-flow min-cut: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(13 intermediate revisions by 2 users not shown)
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>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 a [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flow]]. Then the following three statements are equivalent:
# <math>f</math> is maximum.
# The [[Basic flow definitions#Flow value|flow value]] of <math>f</math> is maximum among all [[Basic flow definitions#Feasible flow|feasible <math>(s,t)</math>-flows]].
# There is a [[Basic flow definitions#Cuts and saturated cuts|saturated cut]].
# There is a [[Basic flow definitions#Cuts and saturated cuts|saturated cut]].
# There is no [[Basic flow definitions#Flow augmenting path|flow-augmenting path]].
# There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>.


== Proof ==


is a saturated cut if, and only if, there is no augmenting -path.
First suppose there is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>. Let <math>S</math> denote the set of all nodes reachable from <math>s</math> via flow-augmenting paths, and let <math>T:=V\setminus S</math>. Then we have <math>s\in S</math> and <math>t\in T</math>. Obviously, <math>(S,T)</math> is [[Basic flow definitions#Cuts and saturated cuts|saturated]].


Proof:
Next suppose there is a [[Basic flow definitions#Cuts and saturated cuts|saturated]] cut. No flow <math>f'</math> can carry more units of flow value from <math>s</math> to <math>t</math> than the capacity of any [[Basic flow definitions#Cuts and saturated cuts|<math>(s,t)</math>-cut]] allows. Consequently, <math>f</math> is maximum.
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:
Finally suppose <math>f</math> is maximum. Clearly, then a [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math> cannot exist.
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.

Latest revision as of 09:29, 3 January 2015

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{ 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 a feasible [math]\displaystyle{ (s,t) }[/math]-flow. Then the following three statements are equivalent:

  1. The flow value of [math]\displaystyle{ f }[/math] is maximum among all feasible [math]\displaystyle{ (s,t) }[/math]-flows.
  2. There is a saturated cut.
  3. There is no flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math].

Proof

First suppose there is no flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math]. Let [math]\displaystyle{ S }[/math] denote the set of all nodes reachable from [math]\displaystyle{ s }[/math] via flow-augmenting paths, and let [math]\displaystyle{ T:=V\setminus S }[/math]. Then we have [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\in T }[/math]. Obviously, [math]\displaystyle{ (S,T) }[/math] is saturated.

Next suppose there is a saturated cut. No flow [math]\displaystyle{ f' }[/math] can carry more units of flow value from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] than the capacity of any [math]\displaystyle{ (s,t) }[/math]-cut allows. Consequently, [math]\displaystyle{ f }[/math] is maximum.

Finally suppose [math]\displaystyle{ f }[/math] is maximum. Clearly, then a flow-augmenting path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] cannot exist.