Page 385 -

MAXIMAL FLOW PROBLEM 365

6 Cairo City Cab Company identified ten primary pickup and drop locations for cab drivers.
In an effort to minimize travel time and improve customer service and the utilization of the
company’s fleet of cabs, management would like the cab drivers to take the shortest
route between locations whenever possible. Using the following network of roads and
streets, what is the route a driver beginning at location 1 should take to reach location
10? The travel times in minutes are shown on the arcs of the network.

15
2 7
5 4
8
3 4 4 10
13 5 7
2
1 15 6 3 6 8 5
5 5
4
10
9
4 9
12
5

7 The City of Copenhagen recently purchased land for a new country park, and park
planners identified the ideal locations for the lodge, cabins, picnic groves, boat dock and
scenic points of interest. These locations are represented by the nodes of the following
network. The arcs of the network represent possible road connections in the park. If the
state park designers want to minimize the total road miles that must be constructed in the
park and still permit access to all facilities (nodes), which road connections should be
constructed?

2 6 12 12
1 8
6 5 3
8 3 11 7
5
8 11 4 6
15
7
2 3 4 9
4 2 2
1 6
1 4 6 3
9 8 10 5
4 14
2
3 5 3 7 4
3
6
9 13

Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has
deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.