876 CHAPTER 13 Graph Theory 35. O’Reilly Auto Parts David, the chief executive officer of O’Reilly Auto Parts, is at his office in Springfield, Missouri, and wishes to visit his company’s distribution centers in the following locations: Bismarck, ND; Carson City, NV; Helena, MT; and Knoxville, TN. He wishes to visit each of these locations and return to his office in Springfield. The one-way flight prices are given in the following table. Bismarck Carson City Helena Knoxville Springfield Bismarck * $431 $483 $476 $378 Carson City $431 * $144 $159 $505 Helena $483 $144 * $542 $492 Knoxville $476 $159 $542 * $459 Springfield $378 $505 $492 $459 * a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of flights on the appropriate edges. * b) Use the nearest neighbor method to approximate the optimal route for David to travel to each city and return to Springfield. Give the cost of the route determined. S B C H K S , , , , , for$1954 c) Randomly select another route for David to travel from Springfield to each of the other cities and return to Springfield and then compute the cost of this route. Compare this cost with the cost determined in part (b). Answers will vary. 36. Wayfair Yilan lives in Boston, Massachusetts, and works for the e-commerce company Wayfair. Yilan wishes to visit company warehouses in the following locations: Madison, WI; Princeton, NJ; Salem, OR; and Walla Walla, WA. The one-way flight prices are given in the following table. m Boston Boston Madison Princeton Salem Walla Walla Boston * $131 $ 256 $298 $ 576 Madison $131 * $ 154 $356 $ 970 Princeton $256 $154 * $353 $1164 Salem $298 $356 $ 353 * $ 179 Walla Walla $576 $970 $1164 $179 * a) Represent this traveling salesman problem with a complete, weighted graph showing the prices of flights on the appropriate edges. * b) Use the nearest neighbor method to approximate the optimal route for Yilan to travel to each city and return to Boston. Give the cost of the route determined. B M P S W B , , , , , for$1393 c) Randomly select another route for Yilan to travel from Boston to each of the other cities and return to Boston and then compute the cost of this route. Compare this cost with the cost determined in part (b). Answers will vary. Challenge Problems/Group Activities 37. Visiting Five Cities List five cities you would like to visit. Search for airline prices between these five cities. Make sure to include the city with the airport nearest your home from which you would start and end your trip. a) Draw a complete, weighted graph that represents these cities and the costs associated with flying between each pair of cities. Answers will vary. b) Use the brute force method to determine the optimal solution to visiting each city and returning home. Answers will vary. c) Use the nearest neighbor method to approximate the optimal solution. Answers will vary. d) How much money does the optimal solution, obtained in part (b), save you over the approximation obtained in part (c)? Answers will vary. 38. Number of Circuits The following tasks are intended to help you understand the formula for determining the number of unique Hamilton circuits in a complete graph. a) Draw a complete graph with three vertices labeled A, B, and C. Assume that you are starting at vertex A and wish to move to another vertex. How many choices do you have for moving to the second vertex? Once you choose the second vertex, how many choices do you have for moving to a third vertex? Multiply the number of choices you had from vertex A by the number of choices you had from the second vertex. Compare the number you obtained with the number of Hamilton circuits determined by using − n( 1)!. * b) Draw a complete graph with four vertices labeled A, B, C, and D. Assume that you are starting at vertex A and wish to move to a second vertex. How many choices do you have for moving to this second vertex? Once you choose the second vertex, how many choices do you have for moving to the third vertex? Once you choose the third vertex, how many choices do you have for the fourth vertex? Multiply the number of choices you had from each vertex together. Compare the number you obtained with the number of Hamilton circuits determined by using − n( 1)!. ⋅ ⋅ = 3, 2, 1; 3 2 1 6. This result is the same as the number of Hamilton circuits in a complete graph with four vertices. c) Repeat this process for complete graphs with five and six vertices. * d) Explain why − n( 1)! gives the number of Hamilton circuits in a complete graph with n vertices. * Sean Pavone/Shutterstock *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=