878 CHAPTER 13 Graph Theory graph, called a tree, which is also frequently used to represent problems from everyday life. Before we define a tree, let’s look at Example 1, in which we create a tree showing the supervisory relationships at a service company. Example 1 Business Structure Construct a graph to represent the supervisory relationships at Handi Henri’s Repair Service. Henrietta is the president and she has three shift supervisors: Tommy, Patrick, and Susan. Tommy supervises two service specialists: Morris and Winton. Patrick supervises two service specialists: Alicia and Nigel. Susan supervises one service specialist: Rodney. Solution We will construct this graph with three layers, one for each level of em- ployee. The vertices represent people and the edges represent supervisor-supervisee relationships. Start with Henrietta and make edges to each of her three shift supervisors, Tommy, Patrick, and Susan. Then make edges from Tommy to his two supervisees, from Patrick to his two supervisees, and from Susan to her supervisee. 7 Winton Tommy Morris Nigel Patrick Alicia Rodney Susan Henrietta Figure 13.44 Now try Exercise 7 Definition: Tree A tree is a connected graph in which each edge is a bridge. Recall from Section 13.1 that a bridge is an edge that if removed from a connected graph would create a disconnected graph. Thus, if you remove any edge in a tree, it creates a disconnected graph. Since each edge would create a disconnected graph if removed, a tree cannot have any Euler circuits or Hamilton circuits. Fig. 13.45(a) gives four examples of graphs that are trees, and Fig. 13.45(b) gives four examples of graphs that are not trees. E F C A A G E D B D F G B C E A E H B C A B G G F F F E B D G C E A C B D D G I H E E H D F A A C B A B F C F C D D (a) Graphs that are trees (b) Graphs that are not trees Figure 13.45 The graph in Fig. 13.44 is an example of a tree.
RkJQdWJsaXNoZXIy NjM5ODQ=