888 CHAPTER 13 Graph Theory Important Facts and Concepts Examples and Discussion Section 13.1 Paths and Circuits A path is a sequence of adjacent vertices and the edges connecting them. A circuit is a path that begins and ends at the same vertex. Discussion, pages 847–848 Section 13.2 Paths and Circuits An Euler path is a path that passes through each edge of a graph exactly one time. An Euler circuit is a circuit that passes through each edge of a graph exactly one time. Euler’s Theorem For a connected graph, the following statements are true: 1. A graph with no odd vertices (all even vertices) has at least one Euler circuit, which is also an Euler path. An Euler circuit can be started at any vertex, and it will end at the same vertex. Discussion, page 854; Example 1, pages 854–855 Examples 2– 6, pages 855–860 Summary CHAPTER 13 Jefferson City Kansas City Springfield St. Joseph St. Louis Jefferson City * 158 138 215 134 Kansas City 158 * 191 56 249 Springfield 138 191 * 227 218 St. Joseph 215 56 227 * 307 St. Louis 134 249 218 307 * a) Use Kruskal’s algorithm to determine the minimumcost spanning tree that would link each city to create the least expensive recreation trail. * b) If the cost of building such a trail is $9500 per mile, what would be the cost of building the trail determined in part (a)? $4,617,000 32. Light-Rail Transit System The state of Illinois is applying for a grant to connect several metropolitan areas of the state with a light-rail transport system. The cities involved are Urbana, Chicago, Peoria, Rockford, and Springfield. The distances in miles between these cities are given in the following table. Urbana Chicago Peoria Rockford Springfield Urbana * 135 89181 86 Chicago 135 *170 85 202 Peoria 89 170 * 129 74 Rockford 181 85129 * 193 Springfield 86202 74193 * a) Use Kruskal’s algorithm to determine the minimumcost spanning tree that would link each city using the shortest distance. * b) What would be the total distance of the light-rail transportation system determined in part (a)? 374 miles Challenge Problems/Group Activities 33. Computer Network Create a minimum-cost spanning tree that would serve as the least expensive way to create a computer network among the five largest cities in your state. Assume that the cost per mile is the same regardless of the path taken. Answers will vary. 34. College Structure Create a tree that shows the administrative structure at your college or university. Start with the highest-ranking officer (that is, president, chancellor, provost) and work down to the department leader level. Answers will vary. 35. Sidewalk Covers Create a minimum-cost spanning tree that would serve as the least expensive way to provide sheltered sidewalks between major buildings on your college campus (see Example 6 on page 882). Assume that the cost per foot is the same regardless of the path taken. Answers will vary. Research Activity 36. Joseph Kruskal Write a research paper on the life and work of Joseph Kruskal, who developed Kruskal’s algorithm. *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=