846 CHAPTER 13 Graph Theory MATHEMATICS TODAY Graph Theory Representations Graphs consisting of points called vertices and lines called edges can represent numerous applications used in many professions. Chemists use graphs to sketch atoms in a molecule. Engineers use graphs in schematic drawings of electrical networks. Genealogists use graphs to represent family trees. Transportation officials use graphs to show airline, railway, and ground transportation routes. Industrial scientists use graphs to represent human and machine interaction times in factories. All these applications can be represented and studied with the branch of mathematics called graph theory, the origins of which can be traced back to Leonhard Euler (1707–1783). The subway map shown above for the city and surrounding area of Washington, DC, is a graph of vertices and edges. Why This Is Important Graph theory is an important tool that uses simple diagrams for representing key aspects of many problems. Example 3 Representing a Floor Plan Fig. 13.9 shows the floor plan of the Phenomenal Phitness gym. Use a graph to represent the floor plan. Locker Room A Outside Sierra’s Training Room Keegan’s Training Room Cycling Room Locker Room B Health/Weight Room Group Exercise Room Figure 13.9 Solution To create a graph, we will use vertices to represent each of the seven rooms and a separate vertex to represent the outside of the gym. To label the vertices, we will use the first letter of the room names along with H for the health/ weight room, A for locker room A, B for locker room B, and O for the outside of the gym. Next, connect the vertices with edges. To determine placement of the edges within the graph, visualize walking through various doorways in the building. For example, since a person can walk from the Group Exercise room directly into either the health/weight room or into locker room A, there is an edge between G and H, and an edge between G and A. The resulting graph is shown in Fig. 13.10. Notice that since the health/weight room has two separate doorways that lead to the outside of the building, there are two separate edges that connect vertices H and O. C S B H A O K G Figure 13.10 7 Now try Exercise 35 In Example 3, we placed the vertex O, for outside, near the top of the graph. If vertex O had been placed elsewhere, the graph would look different, but the graph would still represent the floor plan shown in Fig. 13.9. Example 4 Representing a Neighborhood Fig. 13.11 shows a sketch of the Greenbriar subdivision of homes. Use a graph to represent the streets of this neighborhood. Jorik/Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=