# Flows in directed graphs

## Contents |

### Introduction

Let *G* = (*V*,*E*) be a directed graph with two distinguished nodes, a source *s* ∈ *V* and a sink *t* ∈ *V*. Let be a capacity function that assigns nonnegative weights to the edges of the graph. Further, for each node *v* ∈ *V* let

- be the set of all outgoing edges of
*v*, - be the set of all ingoing edges of
*v*.

Let *f*(*e*) indicate the 'quantity' passing an edge *e* ∈ *E*. Moreover let denote the value of a function *f* for all subsets *A* ⊆ *E*.
Now we can define *s* − *t* flows on the directed graph *G* = (*V*,*E*).

### Definition Flow

A function is called*(or simply*

*s*−*t*flow*flow*) if the following conditions are satisfied:

- for all edges
*e*∈*E*. - for all nodes
*v*∈*V*\{*s*,*t*}.

The first condition is called capacity constraint. The second condition is a
flow conservation constraint — it is also known as *Kirchhoff'*s law. It guarantees that the total flow into any node *v* ∉{*s*,*t*} is equal to the total flow out of *v*.

### Example 1

We investigate the following directed graph *G* = (*V*,*E*) with capacities *c*(*e*) = 1 for all edges *e* ∈ *E*.

Then the function with

- ,
- ,

satisfies the flow conditions (see Definition 1), i.e., *f* is an *s* − *t* flow in the graph *G* = (*V*,*E*).

The value | *f* | = *f*(δ^{ + }(*s*)) − *f*(δ^{ − }(*s*)) is called value of the flow *f*. For instance, the value of the flow in Example 1 is 1.5. A *maximum s − t flow* is a

*s*−

*t*flow with maximum value.

Let δ^{ + }(*S*) = {(*v*,*w*) ∈ *E*: *v* ∈ *S*, *w* ∉ *S*} and δ^{ − }(*S*) = {(*v*,*w*) ∈ *E*: *v* ∉ *S*, *w* ∈ *S*} be the set of all outgoing and ingoing edges of *S* ⊆ *V*, respectively. For instance we choose *S* = {*s*,1,2} in Example 1. That implies δ^{ + }(*S*) = {(2,3),(1,*t*)} and δ^{ − }(*S*) = {(3,*s*),(3,1)}.

**Lemma 1.** Let *f* be an *s* − *t* flow in *G*. Then for all subsets *S* ⊆ *V* *w**i**t**h* *s* ∈ *S*, *t* ∉ *S* it holds

- .

A subset *S* ⊆ *V* with *s* ∈ *S*, *t* ∉ *S* is called *s* − *t* cut with the value
. A *minimum s − t cut* is a

*s*−

*t*cut with minimum value. The flow on the

*s*−

*t*cut

*S*is

*f*(δ

^{ + }(

*S*)) −

*f*(δ

^{ − }(

*S*)).

Because of the capacity constraint of flows the following
inequality is satisfied for all *s* − *t* cuts *S*:

- .

Obviously the value of an *s* − *t* flow *f* on any *s* − *t* cut *S* with *S* ⊆ *V* cannot exceed the capacity of this *s* − *t* cut.

Thus it is

- .

Herein the inequality can be replaced by equality. This is stated in the famous max-flow min-cut theorem which was proved by Ford/Fulkerson.

**Theorem 2.** Let *G* = (*V*,*E*) be a directed graph with *s*, *t* ∈ *V*, *s* ≠ *t*, and . Then the maximum value of an *s* − *t* flow in *G* is equal to the minimum value of an *s* − *t* cut.

### Example 2

We investigate the graph of Example 1 again.
Then with:

*f*^{ * }(*s*,1) = *f*^{ * }(*s*,2) = *f*^{ * }(1,*t*) = *f*^{ * }(2,3) = *f*^{ * }(3,*t*) = 1 (red edges in the above figure)

and is a **maximum flow** with value | *f*^{ * } | = 2.

Now we want to prove that *f*^{ * } is indeed maximum. For this we use the max-flow min-cut theorem. We consider the *s* − *t* cut *S* = {*s*}. It holds *c*(δ^{ + }(*s*)) = 2.
Since this is an upper bound to the values of the *s* − *t* flow, *f*^{ * } is maximum.

For more details we refer the interested reader to the standard textbook on network flows by [Ahuja et al. (1993)].