MATH SHEET 10

1. For the above weighted graph, use the Brute Force Algorithm to find an optimal Hamilton Circuit stating at Vertex C.

2. You work at UPS and the company has decided to add a new truck route that will cover 9 cities in Japan. Assume each city is connected to each city. You want to design the route in the most efficient way so that the truck will never have to visit a city more than once, except for Tokyo (where the headquarters is located.) Your boss wants the optimal route. Which algorithm should you use to answer your boss's question?

3. Suppose you are planning a trip around the world. Below is a table of the distances (in miles) between the cities you want to visit. Assume that you will start and end your trip in New York City.

Find the nearest-neighbor tour with New York as the starting city.