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.) |