Class Notes
(807,639)

Canada
(492,765)

University of Toronto Scarborough
(30,793)

Computer Science
(300)

CSCC73H3
(10)

Vassos Hadzilacos
(10)

Lecture

# Solutions to A4

Unlock Document

University of Toronto Scarborough

Computer Science

CSCC73H3

Vassos Hadzilacos

Fall

Description

Computer Science C73 Nobermber 30, 2010
Scarborough Campus University of Toronto
Solutions to Homework Assignment #4
Answer to Question 1.
a.
v
0.5/1 1/1
s t
0.5/1 0.5/1
u
The label “f/c” on each edge indicates that the edge has capacity c, f of which is used by the ﬂow. It
is easy to check that the speciﬁed ﬂow is proper (i.e., it satisﬁes the capacity and conservation constraints).
It is a maximum ﬂow because it has value 1, and the (s,t)-cut ({s,u,v]},{t}) has capacity 1.
b. For any set of vertices S, let out(S) be the set of edges with tail in S and head not in S. Let
(S ,T ) be a min-cut of the ﬂow graph G, and f ∗ be a max-ﬂow in G. By Proposition 7.6 in KT ,
∗ ▯ ∗ ▯ ∗ ∗ ▯
V (f ) = e∈out(S )f (e) − e∈out(T )f (e). By the max-ﬂow-min-cut theorem, V (f ) = e∈out(S )c(e).
Thus, by the capacity constraint, every edge in out(S ) is saturated in f . By assumption, V (f ) > 0,
∗ ∗ ∗
and so there is some e ∈ out(S ) such that f (e) > 0. As we just saw, such an edge is saturated in f , i.e.
f (e) = c(e). Since all capacities are integers by assumption, f (e) is a positive integer, as wanted.
c. We will prove, by induction on k, that for each integer k such that 0 ≤ k ≤ m, there is an integral ﬂow
f such that V (f) = k.
Basis. k = 0. Take f(e) = 0 for each edge e. This trivially satisﬁes the capacity and conservation
constraints. Thus it is an integral ﬂow whose value is 0, as wanted.
Induction Step. Step Let k be an arbitrary integer such that 0 < k ≤ m. Assume that there is an
′
integral ﬂow f whose value is k − 1. We will prove that there is an integral ﬂow f whose value is k. Since
f has value k − 1 < m, it is not a maximum ﬂow. Therefore, the residual graph G ′has an (s,t)-path,
′ f
say p. Because f is an integral ﬂow, the residual capacities of G f′ are integers, and so the bottleneck of p
has residual capacity at least 1. Let
f (e) + 1, if e is a forward edge on p
f(e) = f (e) − 1, if the reverse of e is a backward edge on p
′
f (e), otherwise
The function f is a ﬂow in G: It satisﬁes the capacity constraint because the residual capacity of every
edge on p in G f′ is at least 1. It satisﬁes the conservation constraint because f does: For each vertex on
path p (other than s and t), the incoming traﬃc changes by v, for some v ∈ {−1,0,+1}, if and only if the
outgoing traﬃc also changes by v; while for each vertex not on p, neither the incoming nor the outgoing
′ ′
traﬃc changes. Since f is an integral ﬂow, so is f. Furthermore, V (f) = V (f ) + 1 = k.
1 Answer to Question 2.
a. In Dijkstra’s algorithm we keep track of a set S of vertices, and for each vertex v two quantities, d(v)
and p(v): d(v) is the minimum length of any path from s to v among all paths whose intermediate vertices
(i.e., vertices other than v) are in S, or ∞ if no such path ▯xists; and p(v) is the predecessor of v on such
a path. (The length of a path p is the sum of the lengths of its edges:).)
e on p
The set S starts oﬀ containing only s (in which case the corresponding d and p values are straightforward
to compute). In each iteration we augment S by a vertex u, currently not in S, that has minimum d(u),
and we update d(v) and p(v) for each vertex v adjacent to u to reﬂect the change in S.
In our modiﬁcation of Dijkstra’s algorithm, instead of d(v) we keep track of b(v): the maximum
bottleneck of any path from s to v among all paths whose intermediate vertices are in S, or 0 if no such
path exists. (The bottleneck of a path p is the minimum capacity of its edge on pe).) In each
iteration we augment S by a vertex u, currently not in S, that has maximum b(u). The modiﬁed algorithm
is shown below:
S := {s}
for each vertex v do
if v is adjacent to s then b(v) := c(s,v); p(v) := s
else b(v) := 0; p(v) := nil
while S ▯= V do
let u be a vertex not in S that has maximum b(u)
S := S ∪ {u}
for each vertex v adjacent to u do
▯ ▯ ▯ ▯
if b(v) < min b(u),c(u,v) then b(v) := min( b(u),c(u,v) ; p(v) := u
b. Let S be the set of vertices fn G that are reachable from s using edges with residual capacity more
than δ; let T be the remaining vertices. Clearly, s ∈ S; by the deﬁnition of δ, t ∈ T. Thus, (S,T) is an
(s,t)-cut of G.
Let out(S) be the set of edges in G with tail in S and head in T; out(T) is deﬁned similarly. (Note that
in these deﬁnitions we are considering edges in the ﬂow graph G, not the residfal graph G .)
Claim. For every e ∈ out(S), f(e) ≥ c(e) − δ; and for every e ∈ out(T), f(e) ≤ δ.
Proof of Claim. If (u,v) ∈ out(S) and f(u,v) < c(e)−δ, thfn G has a forward edge (u,v) with residual
capacity more than δ. Since u ∈ S, v is also reachablf in G from s using edges with residual capacity
more than δ, and therefore v ∈ S — contradicting that (u,v) ∈ out(S). Similarly, if (u,v) ∈ out(T) and
f(u,v) > δ, then Gf has a backward edge (v,u) with residual capacity more than δ. Since v ∈ S, u
is also reachable in G from s using edges with residual capacity more than δ, and therefore u ∈ S —
f
contradicting that (u,v) ∈ out(T).
We now have:
▯ ▯
V (f) = f(e) − f(e) [KT (7.6)]
e∈out(S) e∈out(T)
▯ ▯ ▯ ▯
≥ c(e) − δ − δ [above Claim]
e∈out(S) e∈out(T)
▯ ▯
= c(e) − δ
e∈out(S) e∈out(S)∪out(T)
▯
≥ c(e) − m ▯ δ [≤ m edges cross cut (S,T)]
e∈out(S)
∗
≥ V (f) − m ▯ δ
where, in the last inequality, we use the fact that the value of any ﬂow (in particular f ) is at most the
∗
capacity of any cut (in particular (S,T)). Rearranging, we get V (f ) − V (f) ≤ m ▯ δ.
2 c. Let b be the bottleneck of P, the maximum-bottleneck s-to-t augmenting path in G . Therefore, evfry
s-to-t path in G hfs an edge with residual capacity at most b. By part (b),
V (f ) − V (f) ≤ m ▯ b (1)
′
Let f = Augment(f,P). Thus,
V (f ) = V (f) + b (2)
Therefore,
∗ ′ ∗ ▯ ▯
V (f ) − V (f ) V (f ) − V (f) + b
V (f ) − V (f) = V (f ) − V (f) [by (2)]
b
= 1 − ∗
V (f ) − V (f)
≤ 1 − b [by (1)]
mb
= 1 − 1
m
▯ ▯
Rearranging, we get V (f ) − V (f ) ≤ V (f ) − V (f) ▯ (1 − 1)
m
d. Let f be the trivial ﬂow (that carries no traﬃc in any edge), and f be the ﬂow after i augmentation
0 i
steps, where in each step we choose the max-bottleneck augmenting path. By part (c) and induction,
∗ ▯ ∗ ▯ i i −i/m
V (f ) − V (f )i≤ V (f ) − V (f )0▯ (1 − 1/m) . Note that V (f ) = 0 an0 (1 − 1/m) < e (since
1/m ▯= 0, and 1 − x < e −x for all x ▯= 0). Thus, V (f ) − V (f ) < V (f ) ▯ e∗ −i/m . Letting i = mlnC,
∗ ∗ i
we get V (f ) − V (f )

More
Less
Related notes for CSCC73H3