Question 2.71

41. The following table shows the mileage between four cities: Springfield, Ill. (); Urbana, Ill. (); Effingham, Ill. (); and Indianapolis, Ind. ().

72

— 147 92 79
147 — 190 119
92 190 — 88
79 119 88 —
  1. Represent this information by drawing a weighted complete graph on four vertices.
  2. Use the weighted graph in part (a) to find the cost of the three distinct Hamiltonian circuits in the graph. (List them starting at .)
  3. Which circuit gives the minimum cost?
  4. Would there be any difference in parts (b) and (c) if the starting vertex were at ?
  5. If one applies the nearest-neighbor method starting at , what circuit would be obtained? Does the answer change if one applies the nearest-neighbor algorithm starting at ? At ? At ?
  6. If one applies the sorted-edges method, what circuit would be obtained? Does one get the optimal answer?

41.

(a) Possible drawings include the following:

image

(b) Tour 1: : 480

Tour 2: : 504

Tour 3: : 446

(c) Tour 3

(d) No

(e) Tour 1; yes; yes; no

(f) Tour 2; no