Class Notes (807,639)
CSCC73H3 (10)
Lecture

# Solutions to A4

5 Pages
261 Views

School
University of Toronto Scarborough
Department
Computer Science
Course
CSCC73H3
Professor
Semester
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

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.