Editing Max-flow min-cut theorem (section)

==Definitions and statement==

The theorem equates two quantities: the maximum flow through a network, and the minimum capacity of a cut of the network. To state the theorem, each of these notions must first be defined. 

===Network===

A '''network''' consists of 
* a finite [[directed graph]] {{math|''G'' {{=}} (''V'', ''E'')}}, where ''V'' denotes the finite set of vertices and {{math|''E'' ⊆ ''V''×''V''}} is the set of directed edges;
* a '''source''' {{math|''s'' ∈ ''V''}} and a '''sink''' {{math|''t'' ∈ ''V''}};
* a '''capacity''' function, which is a mapping <math>c:E\to\R^+</math> denoted by {{mvar|c<sub>uv</sub>}} or {{math|''c''(''u'', ''v'')}} for {{math|(''u'',''v'') ∈ ''E''}}. It represents the maximum amount of flow that can pass through an edge.

=== Flows ===
A '''flow''' through a network is a mapping <math>f:E\to\R^+</math> denoted by <math>f_{uv}</math> or <math>f(u, v)</math>, subject to the following two constraints:
# '''Capacity Constraint''': For every edge <math>(u, v) \in E</math>, <math>f_{uv} \le c_{uv}.</math>
# '''Conservation of Flows''': For each vertex <math>v</math> apart from <math>s</math> and <math>t</math> (i.e. the source and sink, respectively), the following equality holds:<br/><math>\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw}.</math>

A flow can be visualized as a physical flow of a fluid through the network, following the direction of each edge. The capacity constraint then says that the volume flowing through each edge per unit time is less than or equal to the maximum capacity of the edge, and the conservation constraint says that the amount that flows into each vertex equals the amount flowing out of each vertex, apart from the source and sink vertices. 

The '''value''' of a flow is defined by 

:<math>|f| = \sum\nolimits_{\{v : (s,v)\in E\}} f_{sv}=\sum\nolimits_{\{v : (v,t)\in E\}} f_{vt},</math> 

where as above <math>s</math> is the source and <math>t</math> is the sink of the network. In the fluid analogy, it represents the amount of fluid entering the network at the source. Because of the conservation axiom for flows, this is the same as the amount of flow leaving the network at the sink. 

The maximum flow problem asks for the largest flow on a given network. 
<blockquote>
'''[[maximum flow problem|Maximum Flow Problem.]]''' Maximize <math>|f|</math>, that is, to route as much flow as possible from <math>s</math> to <math>t</math>.
</blockquote>

=== Cuts ===
The other half of the max-flow min-cut theorem refers to a different aspect of a network: the collection of cuts. An '''s-t cut''' {{math|''C'' {{=}} (''S'', ''T'')}} is a partition of {{mvar|V}} such that {{math|''s'' ∈ ''S''}} and {{math|''t'' ∈ ''T''}}. That is, an ''s''-''t'' cut is a division of the vertices of the network into two parts, with the source in one part and the sink in the other. The '''cut-set''' <math>X_C</math> of a cut {{mvar|C}} is the set of edges that connect the source part of the cut to the sink part:

:<math>X_C := \{ (u, v) \in E \ : \ u \in S, v \in T \} = (S\times T) \cap E.</math>

Thus, if all the edges in the cut-set of {{mvar|C}} are removed, then no positive flow is possible, because there is no path in the resulting graph from the source to the sink. 

The '''capacity''' of an ''s-t cut'' is the sum of the capacities of the edges in its cut-set,
 
:<math>c(S,T) = \sum\nolimits_{(u,v) \in X_C} c_{uv} = \sum\nolimits_{(i,j) \in E } c_{ij}d_{ij},</math>

where <math>d_{ij} = 1</math> if <math>i \in S</math> and <math>j \in T</math>, <math>0</math> otherwise.

There are typically many cuts in a graph, but cuts with smaller weights are often more difficult to find. 

:'''Minimum s-t Cut Problem.''' Minimize {{math|''c''(''S'', ''T'')}}, that is, determine {{mvar|S}} and {{mvar|T}} such that the capacity of the s-t cut is minimal.

=== Main theorem ===
In the above situation, one can prove that the value of any flow through a network is less than or equal to the capacity of any ''s-t'' cut, and that furthermore a flow with maximal value and a cut with minimal capacity exist. The main theorem links the maximum flow value with the minimum cut capacity of the network.

: '''Max-flow min-cut theorem.''' The maximum value of an s-t flow is equal to the minimum capacity over all s-t cuts.