Math 115

Quiz 6

F A E B D C

March 27, 2013 Name:

__ __*key*__ __

1. Does this graph have a Hamilton circuit? If so, find one. If not, carefully explain why not.

*Yes it does. Several – one of which is
AFBCDEA.*

2. “The nearest neighbor is an approximate and efficient algorithm.” Explain in a complete English sentence what this means.

*The nearest neighbor
algorithm is approximate, in the sense that it does not always find the route
with the least possible weight, although it is efficient – so even as the
number of vertices (or locations) grows, the time required to implement this
algorithm does not grow disproportionately large.*

You need to start in DC, visit 5 other cities, and then
return back to DC. The cost of travel
between each pair of cities is shown on the graph below. In each of the following questions determine
the route that you would take (you do *not*
need to find the cost of the trip – only the route)

* Boston 85 New York*

* 140 120 *

* 185 500 220
100*

* 280 300*

*Chicago 150 DC*

* *

* 310 *

* 270*

* *

* 290
275*

*Miami 410 San Fran*

* *

*you** should indicate the order in which you
select the edges.*

3. If you use the __nearest
neighbor__ algorithm, starting in DC,

what route will you take?

The nearest neighbor to DC is NY. From NY the nearest

(unvisited) neighbor is Boston. Then Chicago, San Fran,

Miami and finally back to DC.

4. If you use the __cheapest
link__ algorithm, what route will you take?

*Don’t forget that your
travels must begin and end in DC.*

The cheapest link is Boston-NY, followed by NY-DC, so we
need to be sure to include these edges.
We don’t then need NY-Chi (we don’t need a 3^{rd} flight into or
out of NY) or Bos-DC (it would close a circuit), but
can use DC-Chi. Continuing in this way,
we then pick Chi-SF, Boston-Miami, and finally Miami-SF.

So our route is DC-NY-Boston-Miami-SF-Chicago-DC (or the same in reverse order)