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

NOTE :  partial credit can be earned on #3 and 4 only if it is clear how you found the route, and your technique is correct even if you made an error along the way, so

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 3rd 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)