6.4 Design of an optimum road network Suppose that in Figure 6. 11, the nodes of the graph represent seven towns in a rural area and its links a set of paved roads which could possibly be constructed to connect the towns. Note that some connections (e.g., C to D) cannot be built (owing, perhaps, to such constraints as mountainous terrain). The distances indicated on Figure 6.11 are miles. Suppose now that a regional commission charged with planning the road
network in this area: (1) has a budget sufficient to construct up to a total
of 34 miles of paved roads; and (2) wishes to minimize the quantity
Z = Find the optimum road network for this case. (This is an example of "optimum network design," a class of difficult network problems.) |