Graphs and Their Uses (New Mathematical Library Series, # 34) / Edition 1 available in Paperback
- Pub. Date:
- Mathematical Association of America
Read an Excerpt
Introduction to the First Edition
The term "graph" in this book denotes something quite different from the graphs you may be familiar with from analytic geometry or function theory. The kind of graph you probably have dealt with consisted of the set of all points in the plane whose coordinates (x,y), in some coordinate system, satisfy an equation in x and y. The graphs we are about to study in this book are simple geometrical figures consisting of points and lines connecting some of these points; there are sometimes called "linear graphs". It is unfortunate tat two different concepts bear the same name, but this terminology is now so well established that it would be difficult to change. Similar ambiguities in the names of things appear in other mathematical fields, and unless there is danger of serious confusion, mathematicians are reluctant to alter the terminology.
The first paper on graph theory was written by the famous Swiss mathematician Euler, and appeared in 1736. From a mathematical point of view, the theory of graphs seemed rather insignificant in the beginning, since it dealt largely with entertaining puzzles. But recent developments in mathematics, and particularly in its applications, have given a strong impetus to graph theory. Already in the nineteenth century, graphs were used in such fields as electrical circuitry and molecular diagrams. At present there are topics in pure mathematics-for instance, the theory of mathematical relations- where graph theory is a natural tool, but there are also numerous other uses in connection with highly practical questions; matchings, transportation problems, the flow in pipeline networks, and so-called "programming" in general. Graph theory now makes its appearance in such diverse fields as economics, psychology and biology. To a small extent puzzles remain a part of graph theory, particularly if one includes among them the famous four color map problem that intrigues mathematicians today as much as ever.
In mathematics, graph theory is classified as a branch of topology; but it is also strongly related to algebra and matrix theory.
In the following discussion we have been compelled to treat only the simplest problems from graph theory; we have selected these with the intention of giving an impression, on the one hand, of the kind of analyses that can be made by means of graphs and, on the other hand, of some of the problems that can be attacked by such methods. Fortunately, no great apparatus of mathematical computation needs to be introduced.
Table of Contents1. What is a graph?; 2. Connected graphs; 3. Trees; 4. Matchings; 5. Directed graphs; 6. Questions concerning games and puzzles; 7. Relations; 8. Planar graphs; 9. Map coloring.