4.5. Flows in a graph
Let be a directed graph with vertex set V
and edge
. We will study flows in
from a vertex s to a vertex t.
We will call s and t as source
and sink, respectively.
A non-negative function - called flow - f is a defined on the edges. The value is the flow or current in the edge
. For notational simplicity we shall
write
and a similar convention will be used for
other functions.
A flow from s to t has to satisfy the Kirchhoff's current law: the total current flowing into each intermediate vertex (that is different from s and t) is equal to the total current leaving the vertex. This condition is known as the conservation condition.
More formally: if for then we denote by
the „outgoing"
neighbours of x,
the „ingoing" neighbours of x,
then a flow from s to t satisfies the following condition:
for each .
Since
so we find that
The common value
is called the value of f or the amount of flow from s
to t. It is denoted by .
Let , be an edge, then we define a capacity function for
as follows:
.
We shall assume that the current flowing through the edge cannot be more than the capacity
.
The question in hand: what is the maximal flow value from s to t while we have capacity constraints on edges which restrict the current through the edges?
Let be given two subsets X,Y of V, then we write for the set of directed
edges:
If is a function, then we put
If S is a
subset of V containing s but not t then is called a cut separating s from t.
The capacity of a cut is denoted by
.

contains a cut.
It is obvious that the capacity of a cut is at least as large as the value of any flow:
.
Do these values exist?
On one hand side, there are only finitely many cuts, so there is a cut whose capacity is minimal. Therefore the minimum on the left hand side exists.
To prove the existence of the right hand side we start from the
.
Therefore, .
Let be a sequence of flows with
.
Then, by passing to a subsequence, we may assume that for each
the sequence
is convergent, say to
.The function f is a flow with value c,
that is a flow with maximal capacity. So, even if some of the edges have
infinite capacity, there is a flow with maximal value which can be either
finite or infinite.
Theorem 4.14. (Max-flow min-cut theorem.) The maximal flow value from s to t is equal to the minimum of the capacities of cuts separating s from t.
Proof.
We have already seen that there is a flow f with maximal value, say v, and the capacity of every cut is at least v. So, we have to prove that there is a cut with capacity v. We will construct the cut in hand.
We will
define a subset recursively as
follows:
- Let .
- If and
then
.
We will prove that is a cut separating s from t
with capacity
.
- First, we will prove that S is
a cut. To do that we need to prove that .
Suppose the contrary i.e. t belongs
to S. Because of the recursive definition there is a sequence of
vertices
for every i, . Let
Then f can be augmented to a
flow in the
following way:
-
if then increase the flow in
by ε.
-
if then decrease the flow in
by ε.
Clearly, is a flow,
and its value is
, contradicting the maximality of f . So,
and therefore
is a cut, separating s from t.
-
Now, it remains to prove that ,
We know that is equal to the value of the flow from S to
and it is defined in the obvious way:
By the definition of S the first sum is exactly
and each element in the second sum is zero. So, as required.
The critical point of the above construction is the augmentation of the flow. So, if the capacity function is integral, then the value of ε is also integer, and so the construction provides an algorithm for finding a flow with maximal value:
Step 1.
Step 2. Suppose we have constructed , and we have found the set S belonging to
-
If is a maximal
flow, the algorithm terminates.
-
If can be
augmented to a flow
by increasing
the flow along a path from s to t (like in the theorem).
Since is
integer, so
, and the sequence must end in at most
steps.
The following figure shows an example. The values of the flow on the edges are in brackets.

Figure 4.4. A graph with .