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 .

Statement 4.13. If we delete the edges of a cut then no positive valued flow from s to t can be defined on the remainder. Conversely, if F is a set of edges after whose deletion there is no flow from s to t then F

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 .