Introductory Graph Theory

Gary Chartrand

• Publisher: Dover Publications
• Year: 2012
• ISBN:
  9780486134949
• Topic: Technology & Engineering
• Subtopic: Applied Sciences
• Index: Technology & Engineering

Graph theory is used today in the physical sciences, social sciences, computer science, and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively, and informative style.
Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics.
Ten major topics — profusely illustrated — include: Mathematical Models, Elementary Concepts of Graph Theory, Transportation Problems, Connection Problems, Party Problems, Digraphs and Mathematical Models, Games and Puzzles, Graphs and Social Psychology, Planar Graphs and Coloring Problems, and Graphs and Other Mathematics.
A useful Appendix covers Sets, Relations, Functions, and Proofs, and a section devoted to exercises — with answers, hints, and solutions — is especially valuable to anyone encountering graph theory for the first time.
Undergraduate mathematics students at every level, puzzlists, and mathematical hobbyists will find well-organized coverage of the fundamentals of graph theory in this highly readable and thoroughly enjoyable book.

Chapter 1

Mathematical Models

Much of the usefulness and importance of mathematics lies in its ability to treat a variety of situations and problems. The mathematical problems which evolve from the real world have been commonly referred to as “story problems,” “word problems,” and “application problems.” Our goal in this book is to give the real-life problem a mathematical description (or to model it mathematically). Ordinarily, finding a mathematical description is a very complex problem in itself, and there is seldom a unique solution. Indeed, the problem of modeling a real-life situation in a mathematical manner can be so complicated and varied that only the barest introduction is possible at this point.

1.1 Nonmathematical Models

Probably the best way to learn what “mathematical models” are is to look at examples. This is what we shall do in this chapter. We begin, however, by retreating one step to the word “model,” since models need not be mathematical. We shall see that the difficulties involved in “constructing” mathematical models may be very similar to the steps in building nonmathematical models.

What exactly does the word “model” mean? Let us consider some uses of this word. Suppose you, the reader, and your husband (perhaps you have a different “model” of a reader!) have received in the mail a brochure which advertises a new land development near your city, including private houses, apartment complexes, and shopping areas. The brochure shows a map of this area. Curved and straight lines represent roads, rectangles represent houses, and other diagrams represent other aspects of this new development. You know, of course, that the map and what it displays is not the actual land development. It is only a model of the development.

You have been considering moving from your current apartment, so, with the aid of the map, you and your husband drive to the apartment complex. This drive turns out to be more difficult than anticipated since all the roads leading into the area are dirt roads and very bumpy. (The map didn’t mention that!) You arrive at the office of the apartment complex, and in the middle of the room is a large table displaying a miniature model of the entire complex. This allows you to see the location of the apartment buildings as well as the office, the swimming pool, the roads, and the children’s play area. Several things which are important to you (such as the location of laundry facilities and carports) are not shown in the model, so you ask about these.

You are interested in this new apartment complex and you would like to see what a typical 2-bedroom apartment looks like. So you are directed to a model apartment. Although all the apartments available are unfurnished, the model apartment is furnished to help you determine its appearance once you have moved in. However, the model apartment is a bit misleading, for it has been elegantly decorated by a local furniture store while your furniture is perhaps quite ordinary at best.

We have now seen three examples of models. In each case, the model is a representation of something else. Whether the model gives an accurate enough picture of the real entity depends entirely on which features are important to you.

How else is the word “model” used? Perhaps you (a different reader) think of an attractive young woman modeling a swimsuit. In this case, the manufacturer or a department store is trying to sell swimsuits, and rather than displaying them at a counter, they are having a model give you an idea of how the suit would look on your wife (or your sister) if you were to buy it. In this case, the model may not give you a very accurate picture of what the swimsuit will look like on the person for whom it is purchased; on the other hand, you may not care.

Another common use of the word “model” is in “model car” or “model airplane.” Perhaps you’d like to build a model of a 1956 Thunderbird. There are model kits available for this purpose, but these may not be satisfactory if you would like your model to illustrate the dashboard. There must be some limitations on the detail of your model, or otherwise, the only possibility is to purchase your own 1956 Thunderbird.

Intuitively, then, a model is something which represents something else. It may be smaller, larger, or approximately the same size as the thing it represents. It illustrates certain key features (but not all features) of the real thing. What features it possesses depends completely on the construction of the model. Ideally, a model should possess certain predetermined characteristics. Whether such a model can be built is often the crucial problem.

Problem Set 1.1

• 1. Give three examples of models you have encountered. Indicate some pertinent features of each model and describe a feature each model lacks which would be useful for it to possess.
• 2. Give an example of a model which is (a) larger than, (b) approximately the same size as the thing it represents.
• 3. Explain the relationship that radio, television, motion pictures, and the theater have with models. What are some of the pertinent differences in how these media model?
• 4. List some occupations which deal directly with nonmathematical models.

1.2 Mathematical Models

In a mathematical model, we represent or identify a real-life situation or problem with a mathematical system. One of the best-known examples of this representation is plane Euclidean geometry or plane trigonometry, which gives useful results for describing small regions, such as measuring distances. For example, the map of a s...