## Try It Now

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

### Exercises

- 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?
- 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.
- {(0
*.*1*k,*0*.*1*k*) :*k*= 0*,*1*,*2*, ...,*10} - {(0
*.*1*,*0*.*3)*,*(0*.*3*,*0*.*8)*,*(0*.*5*,*0*.*3)*,*(0*.*7*,*0*.*9)*,*(0*.*9*,*0*.*1)} - {(0
*.*0*,*0*.*5)*,*(0*.*5*,*0*.*0)*,*(0*.*5*,*1*.*0)*,*(1*.*0*,*0*.*5)} - {(0
*,*0)*,*(0*.*2*,*0*.*6)*,*(0*.*4*,*0*.*1)*,*(0*.*6*,*0*.*8)*,*(0*.*7*,*0*.*5)}

- {(0
- Consider the network whose maximum capacities are shown on the following graph.

- 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*? - Find a flow augmenting path with respect to
*f*for this network. What is the value of the augmented flow? - Is the augmented flow a maximum flow? Explain.

- A function
- Find maximal flows for the following networks.
- 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.