Page 387 -

MAXIMAL FLOW PROBLEM 367

10 The Metrovision Cable Company just received approval to begin providing cable television
service to a suburb of a large city. The nodes of the following network show the distribution
points that must be reached by the company’s primary cable lines. The arcs of the network
show the number of km between the distribution points. Determine the solution that will
enable the company to reach all distribution points with the minimum length of primary
cable line.

4 3
2 8
9
4 4
2
3
3
4 7 7
3 11
3 6
4
1 2 4 2
2 10
5
4 3
6
5
4
3
4

5

11 The north–south highway system passing through Frankfurt, Germany, can accommodate
the capacities shown.

4
2 5
Flow capacity:
1 1 6 6000 vehicles
2 per hour
1 1
3 3
1 4 6
Entering Leaving
Frankfurt 6 3 Frankfurt
(north) 2 (south)
3
3

Can the highway system accommodate a north–south flow of 10 000 vehicles per hour?
12 If the Frankfurt highway system described in Problem 11 has revised flow capacities as
shown in the following network, what is the maximal flow in vehicles per hour through the
system? How many vehicles per hour must travel over each road (arc) to obtain this
maximal flow?

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.