Max-flow min-cut: Difference between revisions
m (→Proof) |
|||
| (11 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>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 | 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 | # There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] from <math>s</math> to <math>t</math>. | ||
== Proof == | == Proof == | ||
First suppose there is no flow-augmenting path. 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> | 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]]. | ||
Next suppose there is a saturated cut. | 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. | ||
Finally suppose <math>f</math> is maximum. Clearly, a flow-augmenting path cannot exist. | 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. | ||
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:
- The flow value of [math]\displaystyle{ f }[/math] is maximum among all feasible [math]\displaystyle{ (s,t) }[/math]-flows.
- There is a saturated cut.
- 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.