Flow Network - Definition

Definition

is a finite directed graph in which every edge has a non-negative, real-valued capacity . If, we assume that . We distinguish two vertices: a source and a sink . A flow network is a real function with the following three properties for all nodes and :

Capacity constraints:	. The flow along an edge cannot exceed its capacity.
Skew symmetry:	. The net flow from to must be the opposite of the net flow from to (see example).
Flow conservation:	, unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

Notice that is the net flow from to . If the graph represents a physical network, and if there is a real flow of, for example, 4 units from to, and a real flow of 3 units from to, we have and .

The residual capacity of an edge is . This defines a residual network denoted, giving the amount of available capacity. See that there can be a path from to in the residual network, even though there is no path from to in the original network. Since flows in opposite directions cancel out, decreasing the flow from to is the same as increasing the flow from to . An augmenting path is a path in the residual network, where, and . A network is at maximum flow if and only if there is no augmenting path in the residual network.

Should one need to model a network with more than one source, a supersource is introduced to the graph. This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.