Network Flow
A flow network G = (V;E) is a directed graph in which each edge (u, v) ∈ E
an edge (u, v), then there is no edge (v, u) in the reverse direction. If (u, v) ∉ E, then for
has a nonnegative capacity c(u, v)≥ 0. We further require that if E contains
convenience we deûne c(u, v) = 0, and we disallow self-loops. Each flow network contain
two distinguished vertices: a source s and a sink t.
A flow in G is a real-valued function f : V X V→ R that satisûes the following two
properties:
Residual networks
Augmenting paths
Given a üow network G = (V, E) and a flow f , an augmenting path p is a
simple path from s to t in the residual network Gf. By the definition of the residual
network, the flow on an edge (u, v) of an augmenting path may increase by
up to cf (u, v) without violating the capacity constraint on whichever of (u, v)
and (v, u) belongs to the original üow network G.
The maximum amount by which we can increase the flow on each edge in an augmenting
path p the residual capacity of p, given by
Cuts of flow networks
A cut .(S; T) of flow network G =(V;E) is a partition of V into S and
T = V - S such that s ∈ S and t ∈ T .
If f is a üow, then the net üow f (S; T) across the
Cut (S, T) is deûned to be
A minimum cut of a network is a cut whose capacity is minimum over all cuts of
the network.
Max-Flow-Min-CutTheorem
Ford-Fulkerson algorithm
