Cs445 — Homework #6 Due: Last day of class In all questions, unless otherwise specified, we are given a network G(V, E), with a positive capacity c(u, v) assigned to each edge (u, v) ∈ E. 1. Run Ford-Fulckerson Algorithm on the graph shown in the second slide of the network flow lecture. 2. Assume G(V, E) is a network, assume S = {s1 . . . sk } an T = {t1 . . . tk } are subsets of vertices. Suggest an algorithm for finding values p(u, v) for every (u, v) ∈ E such that P P (a) ∀u ∈ / (S ∪ T ) we have v∈V p(v, u) = v∈V p(u, v) (b) ∀u, v ∈ V we have 0 ≤ p(u, v) ≤ c(u, v) (c) XX p(s, v) is as large as possible s∈S v∈V 3. Let G(V, E) be a network flow where the capacity of every edge is 1. Suggest an algorithm that finds in time O(|E|2 ) the cut with smallest capacity (among all possible cuts (S, T ). 4. 26.3-1 from CLRS (Second Edition) 5. Assume a set S of students are standing in the rectangles bounded by Campbell Av, Park Av, 6’st and Speedway Blv. There are many of them, and their locations are arbitrary, fixed, and could not be changed once teams are formed. Your goal is to design an algorithm that partition them into as many as possible teams. Let L denote some length – say 100 yards. The rules for forming teams are (a) Each student could belong to at most one team (b) Students are not allow to move. 1 (c) In each team, one member should be on Speedway Blv, and one on 6’st street. (d) In Each time, each member s (excluding the ones on Speedway and 6’st street) has two other team-members s0 , s00 whose distance from s is ≤ L, and in addition, s0 is to the South of s and s00 is North of s. In other words, each team forms a chain of students, starting at Speedway Blv, ends at 6’th, and distances between consecutive members are all ≤ L. Ignore locations of building — assume students could be placed. Your algorithm should run at O(|S|3 ) or faster. (hint - use flow algorithm, and question 1.) 6. You are given a set B of n points in the plane, and a set R of n points in the plane. Each point is given by its coordinates. Suggest an O(n3 ) time algorithm for determining if there is a 1-1 matching between them, where each red point is match to a blue point whose distance is at most 1 unit away. 7. Given a network flow G(V, E) with source s and sink t, explain how to find a cut (S, T ) such that c(S, T ) ≤ c(S 0 , T 0 ) for any other cut (S 0 , T 0 ). A cut (S, T ) is a partition of V into two sets, where s ∈ S and t ∈ T . 8. Run Edmonds-Karp Algorithm on the given network. Assume the capacity of all edges is 1, and directions of all edges are left to right. As the algorithm progresses, specify flow, residual capacity, and direction of edges in GF . Directions of all edges are left to right. For you convenient, the graph appears several times, so you could write these copies. Show the residual network after each stage, (especially the residual capacities, and directions of edges. s t s t s t s t s t s t s t s t s t s t s t s t

© Copyright 2021 ExpyDoc