844 CHAPTER 13 Graph Theory Example 1 Representing the Königsberg Bridge Problem Using the definitions of vertex and edge, represent the Königsberg bridge problem with a graph. Solution Note that each bridge in Fig. 13.1 connects two pieces of land in a manner similar to an edge connecting two vertices. To begin representing the Königsberg bridge problem as a graph, we will label each piece of land with a capital letter, as shown in Fig. 13.3. Bridge Bridge Bridge Bridge Bridge Bridge Bridge Water C B D A Figure 13.3 Now try Exercise 29 vertices will be referred to using the two vertices. For example, in Fig. 13.2, the edge that connects vertex A to vertex B is referred to as edge AB or as edge BA. The loop in Fig. 13.2 is referred to as edge BB or loop BB. Not every place where two edges cross is a vertex. A dot must be present to represent a vertex. For instance, in Fig. 13.2, even though edges AD and BC cross, since no dot is indicated, the place where these edges cross is not a vertex. With these basic definitions, we can begin using graphs to represent physical settings. A D B C Figure 13.4 Next, we draw edges to represent the bridges. Notice that there are two bridges connecting land A to land B in Fig. 13.3. Therefore, we need two edges to connect vertex A to vertex B in our graph (see Fig. 13.4). Notice that there is one bridge connecting land A to land C in Fig. 13.3. Therefore, we need one edge to connect vertex A to vertex C in our graph. We continue to let edges represent bridges, and the resulting graph is given in Fig. 13.4. Although the picture and the graph do not look very similar, the graph represents the key aspects of the problem: The land is represented with vertices, and the bridges are represented with edges. 7 Graphs are powerful tools in problem solving because they allow us to focus on the key aspects of problems without getting distracted with unnecessary details. Our next three examples show other ways that graphs can be used to represent settings from the physical world. Example 2 Vacationing in the Southwest The Jugo family is vacationing in the southwestern portion of the United States. They plan to visit the states shown in Fig. 13.5. Construct a graph to show the states that share a common border. States whose borders touch only at a single corner point will not be considered to share a common border. RECREATIONAL MATH Online Social Networks Online social networks such as Facebook, X (formally Twitter), TikTok, LinkedIn, Pinterest, Instagram, and Snapchat are Internet sites that share information among a network of people who are linked together. For example, if two Facebook users wish to be linked, they become friends . If a Facebook user posts any comments, pictures, or videos, the information is available to all of that user’s friends. Social networks can be depicted with graphs where the people are represented with vertices and the friendship links are represented with edges. Such a graph for Facebook can be represented only with the help of a very large computer. As of June 2023, Facebook had over 2.99 billion users, with 243.5 million users in the U.S. As of June 2023, Snapchat had 397 million users worldwide. Exercise 44 asks you to draw a graph representing the friendships of six people on Facebook. Samuel Borges Photography/ Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=