Practice Problems for Section 7.2 with Solutions

Section 7.2 Worksheet 1. A circuit in a graph is a path that begins and ends at the same vertex. A) True B) False 2. The traveling salesman problem requires us to find the longest Hamilton circuit. A) True B) False 3. The nearest-neighbor algorithm constructs a(n) _______________ circuit in a complete graph by starting at a vertex. A) Fleury B) Euler C) Vector D) Hamilton 4. When applying the nearest-neighbor algorithm, if there are two or more vertices equally nearby, any one of them may be selected. A) True B) False 5. When applying the cheapest-link algorithm, do not choose an edge that would result in a vertex of degree: 6. The edges in a certain graph represent roads, and the vertices represent intersections. We want to clean all of the roads and not require the street sweeper to move along streets that have already been cleaned. Should we look for an Euler circuit or a Hamilton circuit? 7. The edges in a certain graph represent roads, and the vertices represent intersections. We want to time the traffic signals at each intersection and not visit any intersection twice. Should we look for an Euler circuit or a Hamilton circuit? 8. The edges in a certain graph represent flight paths, and the vertices represent airports (major and rural). We want to look at only the flights from rural airports. Should we look for an Euler circuit or a Hamilton circuit? Page 1 9. Find a Hamilton circuit for the figure below: 10. Find a Hamilton circuit for the figure below: 11. Which of the following is not a Hamilton circuit for the figure below? Page 2 12. A traveling salesman must visit all four cities indicated in the figure below. How many miles does he travel if he starts in A then visits B, C, and D before returning to A? 13. A traveling salesman must visit all four cities indicated in the figure below. How many miles does he travel if he starts in A then visits D, B, and C before returning to A? Page 3 14. A traveling salesman must visit all four cities indicated in the figure below. Which is the shortest route he can take if he wants to begin and end in city A? 15. On a complete graph with n vertices, there are (n-1)!/2 Hamilton circuits starting at a given vertex, not counting reverse routes. If a traveling salesman wanted to make deliveries to nine cities in a region, how many possible routes would he have to check to find the shortest one? Page 4 16. Use the nearest-neighbor algorithm starting at vertex A of the figure below to find an approximate solution to the traveling salesman problem: 17. Use the nearest-neighbor algorithm starting at vertex A of the figure below to find an approximate solution to the traveling salesman problem: Page 5 18. Use the cheapest link algorithm to find an approximate solution to the traveling salesman problem for the figure below: 19. Use the cheapest link algorithm to find an approximate solution to the traveling salesman problem for the figure below: Page 6 20. Either find a Hamilton circuit for the figure below or explain why no such circuit exists: 21. Use the nearest-neighbor algorithm starting at vertex A of the figure below to find an approximate solution to the traveling salesman problem. Also give the distance (assume units are miles). Page 7 22. Use the cheapest-link algorithm to find an approximate solution to the traveling salesman problem for the figure below. Also give the distance (assume units are miles). 23. A salesman must visit all four cities indicated in the figure below. Solve the traveling salesman problem by calculating the mileage for each possible route and indicating which is the shortest. Use A as the starting point. 24. A _______________ is a graph that contains no circuits. 25. Every vertex of a tree is either a parent or a _______________. Page 8 Answer Key 11. ADABCE 1. A 2. B 12. 892 miles 3. D 13. 1239 miles 4. A 14. ABCDA 5. 3 15. 20,160 6. Euler 7. Hamilton 16. ADEBCA 8. Neither 17. ADECBA 9. AFCDEBA 18. ADEBCA 10. No Hamilton circuit exists. 19. ADECBA 20. No Hamilton circuit exists; a Hamilton circuit cannot contain a smaller circuit. 21. Route: ABECDA Distance: 34 miles 22. Route: DCEBAD Distance: 34 miles 23. Route ABCDA: 892 miles (shortest) Route ACDBA: 1127 miles Route ADBCA: 1239 miles 24. Tree 25. leaf Page 9