In graph theory, a cut of a graph or directed graph G=(V,E) is just a partition of the vertices V = Γ ∪ Γ'. The set of edges between an element of Γ and an element of Γ' is also called the cut.
For instance, in the below graph
*
a / \ b
/ c \
*-----O
|\_ |
d| -_ |g
| f \|
*-----O
e
there is a cut between the vertices "*" and the vertices "O". The edges of the cut are b,c,e and f. a and d, between two "*"s, and g, between two "O"s, are not included in the cut.
If G is a capacitated network with capacities c:E→[0,∞), the value of the cut Γ is
∑e ∈ Γ×Γ'c(e)
(the sum of the capacities of all edges going "the right way" across Γ; note that edges from Γ' to Γ are ignored).
The above definition is assymmetrical. Usually, we'll require that the source s∈Γ and the sink t∈Γ'; that helps explain the assymmetry.
These are the two basic questions given a capacitated network:
- max cut - What is the maximal possible value of a cut Γ in the network?
- This is an NP-complete problem.
- min cut - What is the minimal possible value of a cut Γ in the network?
- Duality in linear programming shows that this value is the same as the value of the maximal feasible flow in the graph. The proof of the Ford-Fulkerson algorithm gives an easier way to see this than full-blown linear programming.