13.4 Trees 877 Josefina wishes to install an irrigation system to water the five flower gardens in her backyard. How can Josefina determine the irrigation system that reaches each of her five gardens and has the lowest cost? In this section, we will introduce a type of graph, called a tree, that can help solve the problem facing Josefina. Trees SECTION 13.4 LEARNING GOALS Upon completion of this section, you will be able to: 7 Use trees to represent real-life problems. 7 Solve problems involving spanning trees. Why This Is Important As we will see shortly, trees can be used to represent a wide variety of real-life problems. Trees are used to represent relationships, such as family trees or corporate structures. Trees also are used to determine the cost- effective solutions in a variety of fields including engineering, computer design, architecture, and urban planning. Introduction In this chapter, we have introduced graphs as a means to represent problems from everyday life (Section 13.1). We used graph theory to solve a variety of problems by determining Euler paths and Euler circuits (Section 13.2). We also used graph theory to determine the optimal and approximate solutions to traveling salesman problems using Hamilton circuits (Section 13.3). We now turn our attention to another type of Recreational Mathematics 39. The Icosian Game In 1857, William Rowan Hamilton invented the game called the Icosian Game. The game consisted of a round board with 20 holes and 20 numbered pegs. On the surface of the board was a pattern similar to the graphs we have studied in this chapter (see photo and artwork below). In essence, the object of the game was to use the pegs to form a Hamilton circuit on the graph. The graph below is taken from the Icosian Game. Determine a Hamilton circuit on this graph. AEDNOFGQPTMLCBJK , , , , , , , , , , , , , , , , S R I H A , , , , ; other answers are possible. A B C D E F G H I J K L N M O P Q R S T Research Activity 40. Traveling Salesman Problems Write a paper on traveling salesman problems. Include a brief history of the problems. Also include advances made toward reducing the computational time of determining the optimal solution as well as advances made toward determining better approximate solutions. Royal Irish Academy Sangkhom Sangkakam/ Shutterstock
RkJQdWJsaXNoZXIy NjM5ODQ=