Program Analysis Problem Sheet 11
1. The question considers the Ford-Fulkerson Algorithm. MaximumFlow(G, s, t, c, ):
let f(e) = 0 for all e ∈ E
while there is a path from s to t in the residual graph Gf
let p be a simple path from s to t
f ← augment(G, f, p)
let Gf be the new residual graph associated with f
return f augment(G, f, p):
let the bottleneck edge in p have capacity x for each edge (u, v) in the path p
if (u, v) is a forward edge then f (u, v) ← f (u, v) + x
if (u, v) is a backward edge then f (v, u) ← f (v, u) − x
Term 1, 2015
return f
We will look at how this algorithm would apply to the following network.
v 18 v 25
11 16 12 26 15 16
s v3 t 28 5
32 20 22
v1
v4
source
flow
sink
(a) Show the residual graph that would be produced given the initial zero flow rates in the network. In drawing a residual graph, to compactly show a forward edge with capacity x and a backward edge with capacity y, label the original edge −→x ; ←−y .
(b) Select path (s, v2, v3, t), and show the residual graph that results from augmenting the flow based on this path.
Program Analysis Term 1, 2015 (c) Now select path (s, v3, v5, t), and show the residual graph that results from aug-
menting the flow based on this path.
(d) Nowselectpath(s,v3,v2,v5,t),andshowtheresidualgraphthatresultsfromaug- menting the flow based on this path.
(e) Now select path (s, v1, v4, t), and show the residual graph that results from aug- menting the flow based on this path.
(f) Now select path (s, v1, v3, t), and show the residual graph that results from aug- menting the flow based on this path.
(g) Now select path (s, v1, v3, v2, v5, t), and show the residual graph that results from augmenting the flow based on this path.
(h) Show the flow rates that have been achieved for the network.
(i) Identify a cut of the network that has a cut capacity equal to the maximum flow of the network.
Program Analysis Term 1, 2015 2. Suppose you’re a consultant for the Ergonomic Architecture Commission, and
they come to you with the following problem.
They’re really concerned about designing houses that are “user-friendly,” and they’ve been having a lot of trouble with the setup of light fixtures and switches in newly designed houses. Consider, for example, a one-floor house with n light fixtures and n locations for light switches mounted in the wall. You’d like to be able to wire up one switch to control each light fixture, in such a way that a person at the switch can see the light fixture being controlled.
Sometimes this is possible and sometimes it isn’t. Consider the two simple floor plans for houses in Figure 1. There are three light fixtures (labelled a b, c) and three switches (labelled 1, 2, 3). It is possible to wire switches to fixtures in Fig- ure 1(a) so that every switch has a line of sight to the fixture, but this is not possi- ble in Figure 1fig:3(b).
Let’s call a floor plan, together with n light fixture locations and n switch loca- tions, ergonomic if it’s possible to wire one switch to each fixture so that every fixture is visible from the switch that controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane (the walls), where
the ith wall has endpoints (xi, yi), (x′i, yi′). Each of the n switches and each of the n fixtures is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them does not cross any of the walls.
Give an algorithm to decide if a given floor plan is ergonomic. The running time should be polynomial in m and n. You may assume that you have a subrou- tine with O(1) running time that takes two line segments as input and decides whether or not they cross in the plane.
2 33
(a) Ergonomic (b) Not ergonomic
Figure 1: The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that each fixture is visible from the switch that controls it. (This can be done by wiring switch 1 to a, switch 2 to b, and switch 3 to c.) The floor plan in (b) is not ergonomic, because no such wiring is possible.
a
1** 2
c
*
b
a
1**
c
*
b
Program Analysis Term 1, 2015
3. Consider a set of mobile computing clients in a certain town who each need to be connected to one of several possible base stations. We’ll suppose there are n clients, with the position of each client specified by its (x, y) coordinates in the plane. There are also k base stations; the position of each of these is specified by (x, y) coordinates as well.
For each client, we wish to connect it to exactly one of the base stations. Our choice of connections is constrained in the following ways. There is a range pa- rameter r — a client can only be connect to a base station that is within distance r. There is also a load parameter L — no more than L clients can be connected to any single base station.
Your goal is to design a polynomial-time algorithm for the following problem. Given the positions of a set of clients and a set of base stations, as well as the range and load parameters, decide whether every client can be connected si- multaneously to a base station, subject to the range and load conditions in the previous paragraph.