13.4 Trees 879 Spanning Trees Some applications, like the business structure in Example 1, can be represented with a graph that is a tree. In other applications, the problem may initially be represented with a graph that is not a tree. In this section, to solve certain problems, we will need to remove edges from a graph that is not a tree to form a tree known as a spanning tree. We now define spanning tree. Definition: Spanning Tree A spanning tree is a tree that is created from another graph by removing edges while still maintaining a path to each vertex. Since a spanning tree is a tree, and since a tree cannot have any circuits, a spanning tree cannot have circuits. (a) A D E G F C H B Figure 13.46 (b) F A H C E D G B Example 2 Determining Spanning Trees Determine two different spanning trees for each graph shown in Fig. 13.46. Solution Each of the spanning trees we create will need to have a path connecting all vertices, but cannot have any circuits. To create a spanning tree from a graph, we remove edges one at a time while leaving all the vertices in place. When we remove an edge, we must make sure the edge is not a bridge. Removing a bridge would create a disconnected graph. We need to reduce our original graph to one that is still connected. Keeping these guidelines in mind, we continue removing edges until the remaining graph is a tree. Two spanning trees formed from each graph in Fig. 13.46(a) and (b) are given in Fig. 13.47(a) and (b), respectively. Other spanning trees are possible in each case. A D E G F C H B A D E G F C H B (a) F A H C E D G (b) B F A H C E D G B 7 Now try Exercise 11 Figure 13.47 Notice in all four spanning trees in Example 2 that each edge is a bridge and that no circuits are present. Our next example provides an application of spanning trees. Example 3 A Spanning Tree Problem Stonewood College is considering adding awnings above its sidewalks to help shelter students from the snow and rain while they walk between some of the buildings on campus. A diagram of the buildings and the connecting sidewalks where the awnings are to be added is given in Fig. 13.48. Learning Catalytics Keyword: Angel-SOM-13.4 (See Preface for additional details.)
RkJQdWJsaXNoZXIy NjM5ODQ=