19 Flow II Notes

19: Network Flow II - The Vengeance
CS 473u - Algorithms - Spring 2005

March 28, 2005
1 Previos Lecture
Theorem 1.1 (Max-flow min-cut theorem)
If f is a flow in a flow network G = (V, E) with source s and sink t, then the following
conditions are equivalent:
1. f is a maximum flow in G
2. The residual network Gf contains no augmenting paths.
3. |f | = c(S, T ) for some cut (S, T ) of G. And (S, T ) is a minimum cut in G.
1
2 Accountability
Comic done by Jonathan Shewchuk http://www.cs.berkeley.edu/~jrs/
People that do not know maximum flows: essentially everybody.

Average salary on earth ¡ $5, 000
People that know maximum flow - most of them work in programming related jobs and
make at least $10, 000 a year.
Salary of people that learned maximum flows: > $10, 000
Salary of people that did not learn maximum flows: < $5, 000
Salary of people that know latin: $0 (unemployed)
Thus, by just learning maximum flows you can double your future salary!
2
3 Ford-Fulkerson Algorithm
Ford-Fulkerson(G,s,t)
Init flow f to zero
While ∃ a path pnfrom s to t in Gf o

cf (p) ← min cf (u, v) uv is in p

For each edge uv in p do
f (u, v) ← f (u, v) + cf (p)
f (v, u) ← f (v, u) − cf (p)
Lemma 3.1 If the capacities on the edges of G are integers, then Ford-Fulkerson runs in
O(m |f ∗ |) time, where |f ∗ | is the amount of flow in the maximum flow and m = |E(G)|.
Proof: Observe that the Ford-Fulkerson algorithm perform only substraction/addition and
min operations. Thus, if it finds an augmenting path, then cf (p) must be a positive integer
number. Namely, cf (p) ≥ 1. Thus, |f ∗ | must be an integer number (by induction), and each
interation of the while improves the flow by at least 1. It follows, that after |f ∗ | iterations of
the while the algorithm stops. However, each iteration of the while loop takes O(m) time,
as can be easily verified.
Observation 3.2 (Integrality theorem) If the capacity function c takes on only integral
values, then the maximum flow f produced by the Ford-Fulkerson method has the property
that |f | is integer-valued. Morover, for all vertices u and v, the value of f (u, v) is an itneger.
4 Edmonds-Karp algorithm
Edmonds-Karp algorithm works by modifying the Ford-Fulkerson algorithm so that it always
return the (edge) shortest augmenting path in Gf . This is implemented by finding p using
BFS.
Definition 4.1 For a flow f , let δf (v) be the length of the shortest path from the source s
to v in the residual graph Gf . Each edge is considered to be of length 1.
Lemma 4.2 If the Edmonds-Karp algorithm is run on a flow network G = (V, E) with
source s and sink t, then for all vertices v ∈ V − s, t, the shortest path distance δf (v) in the
residual network Gf increases monotonically with each flow augmentation.
We delay proving this technical lemma. Lets first prove that it is helping in our life.
Lemma 4.3 During the execution of EK algorithm, an edge uv might disappear (and thus
reappear) from Gfi at most n/2 times, where n = |V (G)|.
3
Proof: When − → disppaers that it must be that uv was on the augmenting path p. Further-
uv
more, cf (p) = cf (uv). We continue running EK till uv magically reappear. This means that
before uv reappeared, we handled an augmenting path π that contains the edge − → Let g
vu.
be the flow just after this. We have
δg (u) = δg (v) + 1 ≥ δf (v) + 1 = δf (u) + 2

as Edmonds-Karp is always augmenting along the shortest path. Namely, the distance of
s to u had increased by two between its disappearance and reappearance. Since δ0 (u) ≥ 0
and the maximum value of δ? (u) is n, it follows that uv can disappear and reappear at most
n/2 times during the executation of Edmonds-Karp algorithm.
Observation 4.4 Every time we add an augmenting path during the executation of EK
algorithm, at least one edge disappears from the residual graph G? . The “bottleneck” edge (the
edge that realizes the flow along the augmenting path) along the augmenting path disappears
after we apply the augmenting path.
Lemma 4.5 Edmonds-Karp algorithm handles at most O(nm) augmenting paths before it
stops. In particular, each augmenting path takes O(m) time, and the overall running time
of Edmonds-Karp algorithm is O(nm2 ) time, where n = |V (G)|and m = |E(G)|.
Proof: Every edge might disappear at most n/2 times during EK executation. Thus, there
are at most nm/2 edge disappearences during the executation of the EK algorithm. Each
time we augment a path, an edge disappears. Augmenting a path takes O(m) time, as we
have to perform BFS to find the augmenting path. It follows, that the overall running time
is as claimed.
We are done??
Lemma 4.6 If the Edmonds-Karp algorithm is run on a flow network G = (V, E) with
source s and sink t, then for all vertices v ∈ V − s, t, the shortest path distance δf (s, v) in
the residual network Gf increases monotonically with each flow augmentation.
Proof: Assume for the sake of contradiction that this is false, and let us stop immidately
after it fails. Let g be the flow after, and f the flow before.
Let v be the vertex s.t. δg (v) is minimal and δg (v) < δf (v).
Let p = s → · · · → u → v be the shortest path in Gg from s to v.
Clearly, uv ∈ E(Gg ).
Thus, δg (u) = δg (v) − 1.
By the choice of v, it must be that δg (u) ≥ δf (u). WHY?
If −
→ ∈ E(G ) then
uv f
δf (v) ≤ δf (u) + 1 ≤ δg (u) + 1 = δg (v) − 1 + 1 = δg (v).
This contradicts our assumptions that δf (v) > δg (v).

Thus, it must be that −
→ is not in E(G ). But uv is in E(G ). How can this be?
uv f g
It must be that the augmentation path π used in computing g from f has the edge −
→
vu.
But we always augment only along the shortest path. WHY?
4
Thus,
δf (u) = δf (v) + 1 > δg (v) = δg (u) + 1.
Thus, δf (u) > δg (u). A contradiction. WHY?
5 Maximum Bipartite Matching

Definition 5.1 For an undirected graph G = (V, E) a matching is a subset of edges
M ⊆ E such that for all vertices v ∈ V , at most one edge of M incident on v. A maximum
matching is a matching M such that for any matching M 0 we have |M | ≥ |M 0 |.
A bipartitle graph:
And a maximum matchin in this graph:
A matching is perfect, if it invovled all vertices:
Theorem 5.2 One can compute maximum bipartite matching using network flows.
Proof: We create a new graph, with new source on the length and sink on the right.
Direct all edges from left to right, and set their capacity to 1. See:
1
s t
5
6 Multiple Sources and Sinks
Given several sources and sinks, how can we comptue maximum flow on such a network?
1
s1 t1
s2
t2
1
‘
Idea: Create a super source, that send all tis flow to the old sources, and similarly create
a super sink.
Resulting graph:
1
t1
∞
s ∞
∞
∞
1
t2
1

19 Flow II Notes

Uploaded by

Copyright:

Available Formats

19 Flow II Notes

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

19 Flow II Notes

Uploaded by

Copyright:

Available Formats

19: Network Flow II - The Vengeance

CS 473u - Algorithms - Spring 2005

2. The residual network Gf contains no augmenting paths.

3. |f | = c(S, T ) for some cut (S, T ) of G. And (S, T ) is a minimum cut in G.

Comic done by Jonathan Shewchuk http://www.cs.berkeley.edu/~jrs/

People that do not know maximum flows: essentially everybody.

While ∃ a path pnfrom s to t in Gf o

δg (u) = δg (v) + 1 ≥ δf (v) + 1 = δf (u) + 2

δf (v) ≤ δf (u) + 1 ≤ δg (u) + 1 = δg (v) − 1 + 1 = δg (v).

This contradicts our assumptions that δf (v) > δg (v).

5 Maximum Bipartite Matching

And a maximum matchin in this graph:

A matching is perfect, if it invovled all vertices:

You might also like