Analysis of Algorithms
LECTURE 25
Network Flows I
• Flow networks
• Max flow problem
• Residual network
• Augmenting paths
• Max flow-min cut theorem
Flow networks
Definition. A flow network is a directed graph G = (V, E) with two distinguished vertices: a sourcesandasinkt. Eachedge(u,v)∈Ehas a nonnegative capacity c(u, v). If (u, v) ∉ E, then c(u, v) = 0.
Example: 2 33
s13132t st
2
2
March 3, 2009
2
3
Flow networks
Definition. A positive flow on G is a function p : V × V → satisfying the following:
• Capacity constraint: For all u, v ∈ V, 0 ≤ p(u, v) ≤ c(u, v).
• Flow conservation: For all u ∈ V – {s, t}, p(u,v) − p(v,u) = 0.
v∈V v∈V
The value of a flow is the net flow out of the
source: March 3, 2009
p(s, v) − p(v, s) . v∈V v∈V
3
A flow on a network
positive capacity
flow 2:2
2:3
s 0:1 1:3 2:3 1:2 t
1:3
st
2:2
u
2:3
1:2
Flow conservation (like Kirchoff’s current law): • Flow into u is 2 + 1 = 3.
• Flow out of u is 0 + 1 + 2 = 3.
The value of this flow is 1 – 0 + 2 = 3.
March 3, 2009 4
The maximum-flow problem
Maximum-flow problem: Given a flow network G, find a flow of maximum value on G.
2:2
2:3
s 0:1 0:3 2:3 1:2 t
2:3
st
March 3, 2009
5
2:2
2:2
3:3
The value of the maximum flow is 4.
Flow cancellation
Without loss of generality, positive flow goes either from u to v, or from v to u, but not both.
Net flow from u to v in both cases is 1.
The capacity constraint and flow conservation are preserved by this transformation.
INTUITION: View flow as a rate, not a quantity. March 3, 2009 6
vv
vv
2:3 1:2 1:3 0:2
uu
uu
A notational simplification
IDEA: Work with the net flow between two vertices, rather than with the positive flow.
Definition. A (net) flow on G is a function f : V × V → satisfying the following:
• Capacity constraint: For all u, v ∈ V, f (u, v) ≤ c(u, v).
• Flow conservation: For all u ∈ V – {s, t},
f (u,v) = 0. v∈V
One summation instead of two.
• Skew symmetry: For all u, v ∈ V, f(u, v) = –f(v, u).
March 3, 2009
7
Equivalence of definitions
Theorem. The two definitions are equivalent.
Proof. () Let f (u, v) = p(u, v) – p(v, u).
• Capacity constraint: Since p(u, v) ≤ c(u, v) and
p(v, u) ≥ 0, we have f (u, v) ≤ c(u, v). • Flow conservation:
f(u,v)=(p(u,v)− p(v,u)) v∈V v∈V
• Skew symmetry:
f (u, v) = p(u, v) – p(v, u)
March 3, 2009
= – (p(v, u) – p(u, v)) = – f (v, u).
8
=p(u,v)−p(v,u) v∈V v∈V
Proof (continued)
(⇐) Let
p(u, v) =
f(u, v) if f(u, v) > 0, 0 if f(u, v) ≤ 0.
• Capacity constraint: By definition, p(u, v) ≥ 0. Since f (u, v) ≤ c(u, v), it follows that p(u, v) ≤ c(u, v).
• Flow conservation: If f (u, v) > 0, then p(u, v) – p(v, u) =f(u,v). Iff(u,v)≤0,thenp(u,v)–p(v,u)=–f(v,u) = f (u, v) by skew symmetry. Therefore,
p(u,v) − p(v,u) = f (u,v). v∈V v∈V v∈V
March 3, 2009
9
1:1
1:1
Notation
Definition. The value of a flow f, denoted by | f |,
is given by
f =f(s,v) v∈V
= f(s,V).
Implicit summation notation: A set used in an arithmetic formula represents a sum over the elements of the set.
• Example — flow conservation:
f (u, V) = 0 for all u ∈ V – {s, t}.
March 3, 2009 10
Simple properties of flow
Lemma.
• f (X, X) = 0,
• f (X, Y) = – f (Y, X),
• f (X∪Y, Z) = f (X, Z) + f (Y, Z) if X∩Y = ∅.
Theorem. | f | = f(V, t). Proof.
|f| = f(s,V)
= f (V, V) – f (V–s, V) = f(V,V–s)
= f(V,t)+f(V,V–s–t) = f(V,t).
Omit braces.
March 3, 2009
11
Flow into the sink
2:2
2:3
s 0:1 0:3 1:3 0:2 t
2:3
st
2:2
|f|= f(s,V)=4
3:3
2:2
f(V,t)=4
March 3, 2009
12
Cuts
Definition. A cut (S, T) of a flow network G = (V, E) is a partition of V such that s ∈ S and t ∈ T. If f is a flow on G, then the flow across the cut is f (S, T).
2:2
2:3 2:3
s 0:1 0:3 1:3 0:2 t st
∈S ∈T
2:2
2:2
3:3
f(S,T) =(2+2)+(–2+1–1+2)
=4
13
March 3, 2009
Another characterization of flow value
Lemma. For any flow f and any cut (S, T), we have|f|= f(S,T).
Proof.
March 3, 2009
f (S, T) = f (S, V) – f (S, S) = f (S, V)
= f (s, V) + f (S–s, V) = f (s, V)
= | f |.
14
Capacity of a cut
Definition. The capacity of a cut (S, T) is c(S, T). 2:2
2:3 2:3
s 0:1 0:3 1:3 0:2 t
∈S ∈T
st
2:2
2:2
c(S, T) = (3 + 2) + (1 + 2 + 3) = 11
March 3, 2009
15
3:3
Upper bound on the maximum flow value
Theorem. The value of any flow is bounded above by the capacity of any cut.
Proof.
f = f(S,T)
= f (u,v) u∈Sv∈T
≤ c(u,v) u∈Sv∈T
March 3, 2009
16
= c(S,T).
Residual network
Definition. Let f be a flow on G = (V, E). The residual network Gf (V, Ef ) is the graph with strictly positive residual capacities
cf (u, v) = c(u, v) – f (u, v) > 0. Edges in Ef admit more flow.
Example:
0:1 4 G:u v G:u v
uvfuv 3:5 2
Lemma. |Ef | ≤ 2|E|. March 3, 2009
17
Augmenting paths
Definition. Any path from s to t in Gf is an aug- menting path in G with respect to f. The flow value can be increased along an augmenting path p by cf (p) = min {cf (u,v)}.
(u,v)∈p
3:5 2:6 0:2
Ex.:
c (p) = 2 5:5 2:3
f 24723
G:s t fst
2:5
G: s st
t
March 3, 2009
18
32 12
1:1
1:1
1:1
Max-flow, min-cut theorem
Theorem. The following are equivalent: 1. f is a maximum flow.
2. f admits no augmenting paths.
3. | f | = c(S, T) for some cut (S, T).
Proof (and algorithms). Next time.
March 3, 2009 19