13.1 Graphs, Paths, and Circuits 843 Sapreet is a Girl Scout leader who needs to deliver cookies to eight different homes in her town. Sapreet realizes there are many possible routes to accomplish this task. However, she would like to determine the shortest route to deliver the cookies to all eight homes and return to her home. In this section we will introduce a type of diagram called a graph that can be used to help analyze and solve such problems. Graphs, Paths, and Circuits SECTION 13.1 LEARNING GOALS Upon completion of this section, you will be able to: 7 Represent problems using graphs. 7 Understand paths, circuits, and bridges. Why This Is Important Graphs can be used to help solve everyday problems such as the one described above. Graphs also play an important role in solving problems from many branches of mathematics, science, business, and engineering. A basic understanding of graphs is a powerful problem-solving tool. The study of graph theory can be traced back to the eighteenth century when people of the East Prussian town of Königsberg (now Kaliningrad, Russia) sought the solution to a popular problem. Königsberg was situated on both banks and two islands of the Prigel River. From Fig. 13.1, we see that the sections of town were connected with a series of seven bridges. The townspeople wondered if one could walk through town and cross all seven bridges without crossing any of the bridges twice. This question was presented to Swiss mathematician Leonhard Euler (pronounced “oiler,” 1707–1783; see Profile in Mathematics on page 155). To study this problem, Euler reduced the problem to one that could be represented with a series of dots and lines. This problem came to be known as the Königsberg bridge problem. Bridge Bridge Bridge Bridge Bridge Bridge Bridge Water Island Island Land Land Figure 13.1 We will revisit the Königsberg bridge problem several times in this section and in Section 13.2. Our main focuses in this section are to introduce definitions of graph theory and to explain how these definitions can help represent problems from the physical world. In the next section, we will introduce some basic graph theory used to solve these problems. It should be noted that the graphs we discuss in this chapter are different from the graphs of equations and functions that we discussed in Chapter 6. Graphs A graph is a finite set of points called vertices (singular form is vertex) connected by line segments (not necessarily straight) called edges or arcs. An edge that connects a vertex to itself is called a loop. Vertices, edges, and a loop are displayed in the graph in Fig. 13.2. We generally refer to vertices with capitalized letters. The edge between two C A B D Not a vertex Loop Edge Vertex Figure 13.2 David Grossman/ Alamy Stock Photo
RkJQdWJsaXNoZXIy NjM5ODQ=