All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual

Preview (16 of 500 Pages)

100%

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 1 preview image

Loading page ...

Guide withFull SolutionsforCOMAP’sFor All Practical PurposesTenth EditionLauren FernUniversity of Montana

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 2 preview image

Loading page ...

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 3 preview image

Loading page ...

Table of ContentsPart I:Management ScienceChapter 1: Urban Services1Chapter 2: Business Efficiency21Chapter 3: Planning and Scheduling41Chapter 4: Linear Programming and the Transportation Problem69Part II: Statistics: The Science of DataChapter 5: Exploring Data: Distributions147Chapter 6: Exploring Data: Relationships176Chapter 7: Data for Decisions206Chapter 8: Probability: The Mathematics of Chance223Part III: Voting and Social ChoiceChapter 9: Social Choice: The Impossible Dream247Chapter 10: The Manipulability of Voting Systems275Chapter 11: Weighted Voting Systems301Chapter 12: Electing the President323Part IV: Fairness and Game TheoryChapter 13: Fair Division334Chapter 14: Apportionment348Chapter 15: Game Theory: The Mathematics of Competition373Part V: The Digital RevolutionChapter 16: Identification Numbers389Chapter 17: Encoding Information399Part VI: On Size and GrowthChapter 18: Growth and Form418Chapter 19: Symmetry and Pattern432Chapter 20: Tilings444Part VII: Your Money and ResourcesChapter 21: Savings Models454Chapter 22: Borrowing Models469Chapter 23: The Economics of Resources483

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 4 preview image

Loading page ...

1Chapter 1Urban ServicesChapter OutlineIntroductionSection 1.1Euler CircuitsSection 1.2Finding Euler CircuitsSection 1.3Beyond Euler CircuitsSection 1.4Urban Graph Traversal ProblemsChapter SummaryManagement science, or operations research, is a branch of mathematics that uses mathematical methods tofind optimal solutions to management problems. Some of these problems involve finding efficient routes forservices such as collecting coins from parking meters, collecting garbage, and delivering mail.Themathematical structure known as agraphis useful in analyzing routes.A graph consists of a finite set ofverticestogether with edges connecting (some, all, or no) pairs ofvertices.A path in a graph is a connected sequence of edges that begins and ends at a vertex. A path is calledacircuitif it begins and ends at the same vertex. In many routing applications (e.g., mail delivery or garbagecollection), the best solution would be a circuit that uses each edge (e.g., sidewalk or street) of an appropriategraph exactly once. Such circuits are calledEuler circuits, in honor of the Swiss mathematician Leonhard Euler.In order to have an Euler circuit, a graph must satisfy two conditions: It must beconnected(i.e., it musthave a path between any pair of its vertices); and each of its vertices must have evenvalences(the number ofedges meeting at that vertex).If the graph for a particular routing application does not have an Euler circuit,the best we can hope to do is find a circuit of minimum length. The problem of finding such a circuit isknown as theChinese postman problem. The solution process relies on“eulerizing” agraph, judiciouslyduplicating edges of the graph to produce a connected graph with even valences so that the total length of theduplicated edges (total number if all edges of the graph have the same length) is as small as possible.TheEuler tour in the“new”graph can be traced on the original by interpreting the use of a duplicated edge as areuse of the original edge it duplicates.There are efficient procedures for finding good eulerizations and for solving the Chinese postman problem.The“edge-walker”method in the text is good for rectangular networks. More sophisticated procedures areneeded in general.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 5 preview image

Loading page ...

2Chapter 1 Urban ServicesSkill Objectives1.Determine by observation if a graph is connected.2.Identify vertices and edges of a given graph.3.Construct the graph of a given street network.4.Determine by observation the valence of each vertex of a graph.5.Define an Euler circuit.6.List the two conditions for the existence of an Euler circuit.7.Determine whether a graph contains an Euler circuit.8.If a graph contains an Euler circuit, list one such circuit by identifying the order in which thevertices are used by the circuit, or by identifying the order in which the edges are to be used.9.If a graph does not contain an Euler circuit, add a minimum number of edges to“eulerize”the graph.10.Find an Euler circuit in an eulerized graph and“squeeze”it onto the original graph. Be able to interpret,in terms of the original graph, the use of duplicated edges in the eulerization.11.Identify management science problems whose solutions involve Euler circuits.Teaching Tips1.Theconceptofconnectednesscouldbeexploredfurtherbyconsideringtreesasopposedtocircuits. This could begin to prepare the student for the work on trees in connectedness.2.In preparation for assigning Exercise 12, you may want to explore in class whether the placement of thevertices representing the cities affects the graph. In particular, consider three cities whose positions are collinear.3.Figure 1.13 demonstrates the process of adding an edge in order to eulerize a graph.Students aresometimes confused by the fact that this added edge is curved rather than straight and attempt to attachunwarranted significance to this. A helpful explanation is that it is curved only so that it won’tbe confused withthe original segment.In addition, you may want to emphasize that the curve could be drawn on either side ofthe original edge and that it indicates a retracing of that edge.4.Ask students to construct a graph of a several-block area of their neighborhood and then look for anEuler circuit for the letter carrier to use.If an Euler circuit does not exist, ask students to produce optimaleulerizations.5.An underlying principle of this chapter is the fact that a mathematical model, in this case a graph, is anabstraction of reality.The solution suggested by the model need not imply that streets would be added to anexisting street network simply for the purpose of creating an Euler circuit.6.Emphasize the differences between Skills Check Exercises 27 and 29.The two exercises are askingtwo different questions for the same graph.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 6 preview image

Loading page ...

Guide with Solutions3Research PapersExercise 48 indicates that the problem situation resembles the one that inspired Euler.This refers to thehistorical Königsberg Bridge Problem (mentioned in Spotlight 1.1).You may choose to ask students to researchthe history of this town (once the capital of East Prussia) and this problem. Websites can be found that contain amap of the area, including the bridges. Also, you may choose to ask students to further investigateEuler’s 1736paper on the problem, which was divided into 21 paragraphs.Students also can research the life andcontributions of the French mathematician Louis Poinsot (1777–1859).Other problems posed by Euler, such asthe Thirty-Six Officers Problem, may also be of interest to students.In 2007, UPS implemented an idea to save the company money resulting from rising gas prices. The idea was tominimize the number of left-hand turns.In the first year, this initiative saved the company about 30 millionmiles and about 3.3 million gallons of fuel.Have students research“turn penalties.”They may wish toinclude in their discussion the biography of J. Edgar Hoover entitledNo Left Turns, by Joseph L. Schott.With the rising cost of gas, have students write about how such a plan saves money and reduces emissions.Students may choose to make a map of the city/town in which they live and determine routes that implement thispolicy and see how they compare to routes that don’t.An extension to this paper can be researching the impactof roundabouts on time and cost of traveling.Collaborative LearningEuler CircuitsAs an introduction to this chapter, duplicate the following exercise on Euler circuits and ask your students toanswer the questions after discussing them in groups.(Do not introduce technical terms such as graph, edge,vertex, valence, or Euler circuit yet.)You will find that most of the students are successful in answering questions (a) and (b), but perhaps notquestion (c).If in fact they do have difficulty answering part (c), call their attention to the number ofedges meeting at each of the vertices. (Resist using the wordvalence.)Ask them to count these numbers foreach of the graphs and then try again to answer part (c) by looking for a pattern.Eulerizationa.Which of the following diagrams can be drawn without lifting your pencil from the paper andwithout retracing any lines?b.Which can be drawn as in part (a), but with the additional requirement that you end the drawing at thestarting point?c.Whatdothediagramsthatcouldbedrawninpart(a)haveincommon?Whataboutthediagrams that could be drawn in part (b)?In other words, try to determine simple conditions on a diagram thatenable you to predict, in advance, whether or not it can be drawn according to the requirements in parts (a) or(b).

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 7 preview image

Loading page ...

4Chapter 1 Urban ServicesIn each of the graphs below, an Euler circuit does not exist because there are vertices with odd valences.It is possible to convert such graphs to graphs having all vertices of even valence by duplicating one or moreedges. For example, in the graphverticesAandCeach have valence 3.Hence, if we duplicate edgeAC,we obtain a modified graph in whicheach vertex has an even valence.Do the same for each of the following graphs and then answer the questions that follow.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 8 preview image

Loading page ...

Guide with Solutions51.If a graph has 4 vertices with odd valences, what is the minimum number of duplications necessary toconvert the graph to one in which all of the vertices are of even valence?Can this minimum number always beachieved?2.Take a campus map (often found in the university catalog or directory) and pick out several keylocations (library, dormitories, computer center, bookstore, etc.) and the streets or paths that connect them. Thenask the students whether an Euler circuit exists for this network. If not, how many edges have to be duplicated?By changing landmarks, you can obtain several new problems.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 9 preview image

Loading page ...

6Chapter 1 Urban ServicesSolutionsSkills Check:1.c2.7; 83.b4.35.a6.167.a8.B;E9.c10.7; 711.b12.1; 2; 4; 5; 1013.c14.615.a16.9; 2217.c18.819.c20.a21.422.1223.a24.425.a26.graph; digraph; graph27.b28.9; 1529.a30.13Collaborative Learning:Euler Circuits:a.Diagrams (2), (3), (4), (5), (7), and (8) can be drawn without lifting the pencil from the paper.b.In (4) and (5) you can return to the starting point.c.In part (a), there are at most 2 vertices with odd valences, while in part (b) there are no vertices with oddvalences.Eulerization:(1)Duplicate 1 edge.(2)Duplicate 2 edges.(3)Duplicate 3 edges.(4)Duplicate 9 edges.If there are 4 vertices with odd valences, then there will be aminimumof two duplications. However, this minimumcan’t always be achieved, as we see from number (3).Exercises:1.(a)There are 6 vertices, each marked with a capital letter.(b)There are 9 edges.2.(a)Three ways to get from C to A by traversing 4 edges are:CDBEA andCDFEAandCDEBA(b)Three ways to get from C to A by traversing three edges are:CDBAandCBEAandCDEA

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 10 preview image

Loading page ...

Guide with Solutions7(c)Three ways to start and end at B traversing four edges are:BDFEB andBCDEBandBAEDB3.(a)(b)ADGIJHKLMLKHG(using other edges)HEDEBAis such a path. Four of the edges aredeadheaded.4.(a)There are 9 vertices and 8 edges.(b)You would need to add two edges. One possibility is as follows:(c)There are seven vertices of valence 2 and two vertices of valence 1.5.(a)This diagram fails to be a graph because a line segment joins a single vertex to itself. The definition beingused does not allow this.(b)The edgeECcrosses edgesADandBDat points that are not vertices; edgeACcrossesBDat a point that isnot a vertex.(c)This graph has 5 vertices and 6 edges.6.(a)7 stores(b)10 roads(c)CBFis a path.(d)EDFBis a path.7.(a)8 vertices(b)13 edges(c)A: 4;B:2;C:3;D:3;E:4;F:4;G:3;H: 3(d)A,D, andF(e)E,G, andH

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 11 preview image

Loading page ...

8Chapter 1 Urban Services8.(a)(b)Assuming that no cities are revisited and that one goes directly from an American city to aEuropean one the routes are:NL,NLR, NLB,NLBR,NLRB,ML,MR,MB,MLR,MLB,MRL,MRB,MBL,MBR,MLRB,MLBR,MRLB,MRBL,MBLR, MBRL9.Ehas valence 0;Ahas valence 1;H,D, andGhave valence 2;BandFhave valence 3;Chas valence 5.Eis“isolated.”Emight have valence 0 because it is on an island with no road access.10.(a)Yes.(b)No. There is no way to get fromAtoC,E, orH.(c)No. There is no way to get fromAtoF,H, orE.11.(a)There are 4 vertices and 4 edges.(b)There are 7 vertices and 6 edges.(c)There are 10 vertices and 14 edges.12.(a)There are five paths to choose from if you assume that no cities are revisited and that one goes directlyfrom an American city to a European city.These areMLB,MLRB,MRB,MRLB,andMB.If you assume that youcan travel between Miami and New York prior to going to Europe then you would consider the pathsMNLBandMNLRB. If revisiting a city is allowed, then there are infinitely many paths.(b)There are five paths if domestic travel is not considered and seven paths to choose from if domestic travelis allowed.(c)In such a route, time and probably cost would be greater if you repeat a city prior to getting to thedestination.13.(a)Answers will vary.Possible answers includeCGDBC.(b) (i)BD;BFD(ii)CBF;CGDF;CGDBF(iii)GDBCG14.In any of these graphs, two edges can be removed and the graph will become disconnected. One of thedisconnected pieces will be a single vertex.15. (a)(b)

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 12 preview image

Loading page ...

Guide with Solutions9(c)Note:Drawing and renderings can vary. The text answer for part (c) offers another drawing.Some other graphs for parts (b) and (c) could be as follows:(b)(c)(d)Yes.The sum of the valences of a graph with 8 vertices, each of valence 2, is 16.Thus, all such graphshave 8 edges.16.(a)2 + 3 + 3 + 0 = 8(b)2 + 2 + 2 + 2 + 2 + 1 + 1 = 12(c)28(d)The number we obtain is twice the number of edges in the graph.(e)The fact that the sum of the valences of the vertices of a graph is always twice the number of edges in thegraph follows from noticing that each vertex of an edge contributes a total of two to the sum because the edge hastwo endpoints.17.Remove the two edges dotted in the figure below, and the remaining graph will be disconnected.Note:Other pairs of edges will also disconnect the graph.18. (a)Yes, it is possible.(b)

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 13 preview image

Loading page ...

10Chapter 1 Urban Services19. (a)Yes, it is possible.(b)No. To have an Euler circuit, a graph cannot have odd-valent vertices.20. (a)There are 8 vertices and 16 edges.(b)DGEDHGFAEFBACBHCD21. Drawings can vary. Possible renderings include the following:22.(a)Yes, a disconnected graph can arise.One possible example is shown below:This gives rise to the disconnected graph:(b)(c)The edge might represent a bridge or tunnel.Recently, when a bridge collapsed because it was hit by abarge, there was a major disruption to the communities near the bridge on opposite sides of the river.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 14 preview image

Loading page ...

Guide with Solutions1123.Drawings can vary. Possible renderings include the following:24.The street direction will matter for a problem involving how long it will take to get between two streetintersections and for routing a street sweeper that follows traffic rules. The street direction may not matter for aninspector checking manholes located in the middle of streets or a service that involves walking along either side ofthe street, such as inspecting sidewalks.25. (a)The supervisor is not satisfied because all of the edges are not traveled upon by the postalworker.(b)The worker is unhappy because the end of the worker’s route wasn’t the same point aswhere the workerbegan. The original job description is unrealistic because there is no Eulercircuit in the graph.26.27.There is such an efficient route.The appropriate graph model has an additional edge joining the same pair ofvertices for each of the edges shown in the graph of Exercise 25.Adding those edges gives you the graph forExercise 26. Since this graph is connected and even-valent, it has an Euler circuit, any one of which will provide aroute for the snowplow. Routes without 180-degree turns are better choices. One possible route is indicated by thenumbered routes.28.(a)Pothole inspection or inspecting the centerline for possible repainting because it had faded.(b)Street sweeping, snow removal, and curb inspections in urban areas.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 15 preview image

Loading page ...

12Chapter 1 Urban Services29.30.(a)The graph is a rectangular network with two rows and three columns No extra edgesneed to be added.(b)31.(a)The largest number of such paths is 3. One set of such paths isAGC,AHFC, andABEIJC.(b)This task is simplified by noticing there are many symmetries in this graph.You may notice that startingwithA, there are only three directions to go.Any number of paths greater than three would involve repeating anedge starting fromA.(c)In a communication system such a graph offers redundant ways to get messages between pairs of pointseven when the failure of some of the communication links (edges removed) occurs.32.Both are circuits; however, only graph (b) is an Euler circuit.33.(a)No. It is not possible. There are odd-valent vertices.(b)The minimum number is four.(c)Answers will vary.One solution would involve duplicating edgesCD,DE,FG, andAB.Another possible Euler circuit starting and ending atCisCDEFGHBKGKBAKJFEIJAICAC.Theduplicated edges are shown below:34.Do not choose edge 3, but edges 9 or 10 could be chosen.35.Do not choose edge 2, but edges 1 or 10 could be chosen.

All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Solution Manual - Page 16 preview image

Loading page ...

Guide with Solutions1336.The following diagram shows one of many solutions for Figure 1.17a:The following diagram shows one of many solutionsfor Figure 1.17b:37.38.If one was outlining garden plots with a sprinkler hose, this tour would allow having the hoses as flat aspossible because one hose would not have to cross another hose.39. (a)A,C,E, andHare odd-valent.(b)Two edges,AHandCE, need to be dropped to produce a graph with an Euler circuit. Persons who parkedalong these stretches of sidewalk without putting coins in the meters would not need to fear that they would gettickets.40.The curved edges on the first graph become double-traversals on the straight edges of the second graph.

Preview Mode

This document has 500 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

for All Practical Purposes: Mathematical Literacy in Today's World Tenth Edition Test Bank

Precalculus - Polynomial and Rational Functions

Precalculus - Functions

Precalculus - Exponential and Logarithmic Functions

Math Word Problems - Translating Expressions

Math Word Problems - Equations

Algebra II – Word Problems

Algebra II – Sequences and Series

Algebra II - Segments Lines and Inequalities

Algebra II - Relations and Functions

Company

Explore

Study Tools