Cs445 — Homework #6

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

Download Report