Try It Now

Work these exercises to see how well you understand this material.

Exercises

  1. Find the closest neighbor circuit through the six capitals of New England starting at Boston. If you start at a different city, will you get a different circuit?

  2. Given the following sets of points in the unit square, find the shortest circuit that visits all the points, and find the circuit that is obtained with the strip algorithm.
    1. {(0.1k, 0.1k) : k = 0, 1, 2, ..., 10}
    2. {(0.1, 0.3), (0.3, 0.8), (0.5, 0.3), (0.7, 0.9), (0.9, 0.1)}
    3. {(0.0, 0.5), (0.5, 0.0), (0.5, 1.0), (1.0, 0.5)}
    4. {(0, 0), (0.2, 0.6), (0.4, 0.1), (0.6, 0.8), (0.7, 0.5)}

  3. Consider the network whose maximum capacities are shown on the following graph.

    1. A function f is partially defined on the edges of this network by: f(Source, c) = 2, f (Source, b) = 2, f (Source, a) = 2, and f (a, d) = 1. Define f on the rest of the other edges so that f is a flow. What is the value of f?
    2. Find a flow augmenting path with respect to f for this network. What is the value of the augmented flow?
    3. Is the augmented flow a maximum flow? Explain.

  4. Find maximal flows for the following networks.




  5. Discuss the reasons that the closest neighbor algorithm is not used in the unit square version of the Traveling Salesman Problem. Hint. Count the number of comparisons of distances that must be done.

 


Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.