Introduction to Algorithms, Third Edition

26.1
Flow networks
In this section, we give a graph-theoretic definition of flow networks, discuss their
properties, and define the maximum-flow problem precisely. We also introduce
some helpful notation.
Flow networks and flows
A
flow network
G
D
.V; E/
is a directed graph in which each edge
.u; /
2
E
has a nonnegative
capacity
c.u; /
0
. We further require that if
E
contains an
edge
.u; /
, then there is no edge
.; u/
in the reverse direction. (We shall see
shortly how to work around this restriction.) If
.u; /
62
E
, then for convenience
we define
c.u; /
D
0
, and we disallow self-loops. We distinguish two vertices
in a flow network: a
source
s
and a
sink
t
. For convenience, we assume that each
vertex lies on some path from the source to the sink. That is, for each vertex
2
V
,
the flow network contains a path
s
;
;
t
. The graph is therefore connected
and, since each vertex other than
s
has at least one entering edge,
j
E
j j
V
j 
1
.
Figure 26.1 shows an example of a flow network.
We are now ready to define flows more formally. Let
G
D
.V; E/
be a flow
network with a capacity function
c
. Let
s
be the source of the network, and let
t
be
the sink. A
flow
in
G
is a real-valued function
f
W
V
V
!
R
that satisfies the
following two properties:
Capacity constraint:
For all
u; 
2
V
, we require
0
f .u; /
c.u; /
.