Knowledge
After completing this assignment you will understand:
1. The difference between a Hamilton circuit and minimal spanning tree.
2. How different paths or circuits can result in lower costs of travel.
Skills
After completing this assignment you will be able to:
1. Find a Hamilton circuit using the Nearest Neighbor Algorithm.
2. Create a graph given 5 cities to find a minimal spanning tree.
Please show ALL work in order to receive full credit. (20 points)
Answers only will receive 1 point.
There are two parts to this project. Each one worth 10 points.
1. Darren works for US Paper Products in New York City. His company is investigating locations for a new factory that will produce a line of disposable clothing. The cities Darren needs to visit are Atlanta, Dallas, Philadelphia, and Washington, DC. The one-way flight prices between these cities are given in the table below.
| Cities and Cost of Travel | |||||
| Atlanta | Dallas | New York | Philadelphia | Washington | |
| Atlanta | * | $182 | $197 | $159 | $180 |
| Dallas | $182 | * | $115 | $115 | $110 |
| New York | $197 | $115 | * | $55 | $156 |
| Philadelphia | $159 | $115 | $55 | * | $205 |
| Washington | $180 | $110 | $156 | $205 | * |
a.) Represent the traveling salesman problem with a complete, weighted graph showing the prices of the flights on the appropriate edges.
b.) Use the nearest neighbor method to approximate the optimal route for Darren to travel to each city and return to New York City. Give the cost of the route determined.
c.) Create your own algorithm and see if you can find a route that costs less than the route you calculated in part b.
2. Select 5 students in your class so that no two have the same hometown. Use the internet to find the distances between each pair of towns (MapQuest is a good source to check).
a.) Draw a complete, weighted graph that represents the five towns and the distances between them.
b.) Use Kruskal’s algorithm to determine the minimum cost spanning tree for the complete, weighted graph in part a.
c.) Determine the total distance one would travel along the minimum-cost spanning tree found in part b.