13.3 Hamilton Paths and Hamilton Circuits 873 Exercises Warm Up Exercises In Exercises 1–8, fill in the blanks with an appropriate word, phrase, or symbol(s). 1. Problems that generally involve seeking the least expensive or shortest way to travel among several locations are called traveling _______ problems. Salesman 2. A graph that has numbers along the edges to indicate cost or distance is called a(n) _______ graph. Weighted 3. A path that begins and ends at the same vertex and passes through all other vertices of a graph exactly one time is called a(n) _______ circuit. Hamilton 4. In a traveling salesman problem, the Hamilton circuit with the lowest associated cost or shortest distance is called the _______ solution. Optimal 5. The method discussed in this section that will determine the optimal solution to a traveling salesman problem is the brute _______ method. Force 6. The method discussed in this section that will determine an approximate solution to a traveling salesman problem is the nearest _______ method. Neighbor Practice the Skills In Exercises 7–8, represent the traveling salesman problem with a complete, weighted graph. Show the prices of flights on the appropriate edges. 7. Hawaiian Islands Justice lives on the island of O’ahu and would like to visit family members on the islands of Maui, Kaua’i, and Hawai’i. She would like to visit each of these islands one time and return to her home on O’ahu. The one-way flight prices between each of the four islands are shown in the following table. * Oahu Hawaii Maui Kauai O’ahu (O) * $44 $39 $63 Hawai’i (H) $44 * $72 $67 Maui (M) $39 $72 * $39 Kaua’i (K) $63 $67 $39 * m Kaanapali, Maui 8. Job Interviews Brandon lives in Dayton and has scheduled job interviews in the following cities: Charleston, Tampa, Baltimore, and Nashville. The one-way flight prices between each of the five cities are shown in the following table. * Dayton Charleston Tampa Baltimore Nashville Dayton (D) * $117 $92 $94 $101 Charleston (C) $117 * $71 $62 $76 Tampa (T) $92 $71 * $45 $37 Baltimore (B) $94 $62 $45 * $44 Nashville (N) $101 $76 $37 $44 * In Exercises 9–14, determine two different Hamilton paths in each of the following graphs. 9. A B C D E F G H B A E F G H D C , , , , , , , and H D C G F E A B , , , , , , , 10. A B C D I H F G E A E F B C D I H G , , , , , , , , and 11. A D C F B E H G A B C D G F E H , , , , , , , and E H F G D C A B , , , , , , , 12. A C G D E F B H I A C D H E F B G I , , , , , , , , and B G I F E A D H C , , , , , , , , 13. A J D G H I E B C F AGJDEBCFIH , , , , , , , , , and JDAGFIHEBC , , , , , , , , , SECTION 13.3 C D I H G B A E F , , , , , , , , *See Instructor Answer Appendix Lynn Watson/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=