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 = d(i, j), i, j = A, B, C, D, E, F, G. where d(i, j) is the shortest distance between town i and j measured on the roadway network that will actually be constructed. [If there is no paved path between two towns i and j, d(i, j) is considered infinite. Note that the MST provides the minimum budget for which Z is finite.]

Find the optimum road network for this case. (This is an example of "optimum network design," a class of difficult network problems.)