890 CHAPTER 13 Graph Theory Section 13.4 Kruskal’s Algorithm To construct the minimum-cost spanning tree from a weighted graph: 1. Select the lowest-cost edge on the graph. 2. Select the next lowest-cost edge that does not form a circuit with the first edge. 3. Select the next lowest-cost edge that does not form a circuit with previously selected edges. 4. Continue selecting the lowest-cost edges that do not form circuits with the previously selected edges. 5. When a spanning tree is complete, you have the minimum-cost spanning tree. Examples 5–7, pages 882–884 Review Exercises CHAPTER 13 13.1 In Exercises 1 and 2, create a graph with the given properties. 1. Create a graph with four even vertices, two odd vertices, a bridge, and a loop. * 2. Create a graph with four even vertices and two loops. * In Exercises 3 and 4, use the following graph. A B G C D E F H 3. Determine a path that passes through each edge exactly one time. ECDFEGABHG , , , , , , , , , 4. Is it possible to have a path that begins at vertex A, includes all edges exactly once, and ends at vertex B? No. A path that includes each edge exactly one time would start at vertex E and end at vertex G, or vice versa. 5. Western States Represent the map as a graph where each vertex represents a state and each edge represents a common border between the states. * WA OR CA NV UT AZ ID 6. School Floor Plan The following drawing shows the floor plan of Raintree Montessori School. Construct a graph to represent the school using the letters shown to label the vertices. Use the letter O to label the vertex that represents the outside of the school. Place vertex O near the bottom of the graph. * D E F A B C Outside In Exercises 7 and 8, determine whether the graph shown is connected or disconnected. 7. A D B E F C Connected 8. A C E B F G D Disconnected *See Instructor Answer Appendix
RkJQdWJsaXNoZXIy NjM5ODQ=