Editing Max-flow min-cut theorem (section)

=== 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.