Network Flows

Given a directed Graph G V E start nodes sink node t each edge ett
has an associated non negative capacity cle

For all non edges capacity is 0

3
4 79 capacity of edge et
2

s 2 Et
2
be 4
d
3

Goal Push max possible flow from s to t subject to following constraints

No flow on an edge can exceed capacity

Capacity Constraint
For all e e E fle cle

2 For all vertices except s t flow in flow out

Flow Conservation
for all v s t f u v flu
iton
Assume we send flow 2 across path s b c t Thisflow saturates the
min capacity of the path

However it is a suboptimal choice since now we can only send flow 1 across
path s a c b d t

The graph has max flow 5 given by

edge
34
a
33 _min t flow capacity
1
5 02 It
2 2
34
min cutedge 5 3 3
d

This flow saturates edges a c s b

Removing these edges disconnects
s from t In other words these edges form an s t cut of size 5
 So max s t flow capacity of min s t cut

Max flow Min Cut Theorem

Max s t Flow Capacity min s t cut

Algorithm needs to find flow of value k cut of capacity K

Def 1
An s t cut is a set of edges whose removal disconnects t from s
OR
A partition of V into sets A B such that s A te B
Edges of cut are edges from A to B

Def 2 Capacity of a cut A B

Sum of capacities of all edges going from A to B

Def 3 For any edge u v f u v flu u Skew Symmetry

1 flow on edge from a to v 1 flow on edge from v to u

This is a mathematical convenience The backedge v u need not exist

in original graph
If fag are flows then hefty is given by

h u v flu v
g u v for all pairs u v

Ford Fulkerson Algorithm

Ideal On an path push max possible flow

s t
2 Define residual capacities maybe introduce backedges
on residual graph Define
3 Repeat till sht become disconnected

Why wouldn't we end up with a sub optimal solution

Def Given a flow f in graph G residual capacity of u v c un f u v

Def Residual graph Gf is a directed graph with all edges of positive

residual capacity May include backedges on original graph
 Example
3
4 79
1
5 22 t
2 2
b d 4
3

Sending a flow f of 2 through s b c t results in following residual

graph Gf
3 4 c b c c b f c b
a 1
4 2
1 2 3
3
St at
b d 4
Cf b s c b s f bs
3
0 2 2

Next we send flow f of 3 through s a c b d t resulting in

residual graph Gf

a 3
to t
2
3
SF 3 it
2
b de

There no longer exists an s t path in Ge so we are done

At each step found a new flow along an augmenting path added to

existing flow So max flow is f t 5

Residual flow guarantees flow is legal To implement just use DFS

Need to prove complexity correctness

Complexity of F F
Assume all capacities are integers If algorithm
finds a flow of F then max possible iterations are F since at
each iteration flow goes up by atleast one

Thm On a graph G with integer capacities F F takes 0 Flinthl

 Correctness B
aT 3 C
A
3 Note final
SF 3
3
it residual graphidentifies
2 a cut A B with
be d
3 capacity 5in original
A s a graph This matches the found
G
B b c d t flow Apply max flow min cut Them

The final residual graph must have sht disconnected otherwise could
increase flow from s to t using existing path

Let A be component containing s B contains t

Let c be capacity of the A B cut in original graph

Claim F F finds flow of value c