Math 115
Quiz 6
F A E B D C
October 21, 2009 Name: Answers
1. Does this graph have a Hamilton circuit? If so, find one. If not, explain why not.
It does – several in
fact. One possibility is
AFBCDEA
2. “The cheapest link is an approximate and efficient algorithm.” Explain in a complete English sentence what this means.
“Approximate” means that the algorithm is not guaranteed to find the best (optimal) route, although we do hope that it finds a good one; “efficient” means that even for fairly large graphs we can apply this algorithm in a reasonable amount of time.
You live in Washington, D.C., and want to take a vacation in which you visit friends in 5 different cities, and then return home. The cost of flying between each of these cities is shown below.
|
|
|
|
D.C. |
|
|
This information
is provided on the graph on the back of this sheet |
||
|
|
|
185 |
140 |
280 |
85 |
500 |
||
|
|
185 |
|
150 |
310 |
120 |
275 |
||
|
D.C. |
140 |
150 |
|
290 |
100 |
270 |
||
|
|
280 |
310 |
290 |
|
220 |
410 |
||
|
|
85 |
120 |
100 |
220 |
|
300 |
||
|
|
500 |
275 |
270 |
410 |
300 |
|
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
3. If you use the nearest neighbor algorithm, starting in DC, what route will you take? (Give the route, in the order that you visit the cities. You do not need to find the cost of the trip)
DC-NY-Boston-Chicago-SF-Miami-DC
(Start in DC, and after
each step go on to the cheapest city that you have not yet visited. After you reach Miami, and have visited every
city, then you fly back home)
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 leg is
Bos-NY. Next is NY-DC. The next cheapest leg that we need is
DC-Chicago (there is a cheaper flight from NY-Chicago, but we already 2 flights
for NY – one in, one out – so we don’t need any more); These are followed by Chicago-SF, Bos-Miami,
and finally SF-Miami. Putting all this
together, we get the route:
DC-NY-Boston-Miami-SF-Chicago-DC (or the reverse of this)
140 120 220
300 100 185 280 500
150 310 290 275 270