880 CHAPTER 13 Graph Theory Administration Library Cafeteria Technology Science Mathematics Health English Figure 13.48 Originally, the president of the university wished to have awnings placed over all the sidewalks shown in Fig. 13.48, but that was determined to be too costly. Instead, the president has proposed to place just enough awnings over a select number of sidewalks so that, by moving from building to building, students would still be able to reach any location shown without being exposed to the elements. a) Represent all the buildings and sidewalks shown with a graph. b) Create three different spanning trees from this graph that would satisfy the president’s proposal. Solution a) Using letters to represent the building names, vertices to represent the buildings, and edges to represent the sidewalks between buildings, we generate the graph in Fig. 13.49. S T A M H C L E Figure 13.49 b) To create a spanning tree we remove nonbridge edges until a tree is created. Three possible spanning trees are given in Fig. 13.50; however, many others are possible. S M H C L E T A S C L E T A M H S M H C L E T A Figure 13.50 7 Now try Exercise 13 Example 3 shows us how spanning trees can be used to represent a real-life problem. However, the president of Stonewood College still has a problem: Which sidewalks in Fig. 13.49 should be chosen to cover with awnings (or which spanning tree should be selected)? Problems like the one faced by Stonewood College usually have Profile in Mathematics Solomon Lefschetz Solomon Lefschetz (1884–1972) was born in Moscow, studied engineering in Paris, and moved to the United States in 1907. After a laboratory accident claimed both his hands and forearms, Lefschetz turned to mathematics. Lefschetz’s work gained him worldwide recognition in algebraic geometry, topology, and nonlinear differential equations. Lefschetz probably will be remembered most for his reaction to the Soviet Union’s launching of the satellite Sputnik . Lefschetz believed that the gap between U.S. and Soviet technology was a result of the Soviet superior knowledge of nonlinear differential equations. To help close this gap, Lefschetz came out of retirement to establish and direct a group of 17 research scientists at the Martin Company’s Research Institute for Advanced Study in Baltimore. At the age of 81, Lefschetz was awarded the national Medal of Science for his role in mathematics and science development in the United States. FPG/Archive Photos/Getty Images
RkJQdWJsaXNoZXIy NjM5ODQ=