This eBook is written for the Internet!
Mathematics has always provided a rich source of solutions to problems in numerous fields: physics, chemistry, biology, anthropology, psychology, economics, sociology, and geography, among others. Too often, however, the mathematician removes the problem from its applied setting, solves it in complete generality, and leaves the solution accessible only to a select few. Broadly viewed, different branches of mathematics fit different categories of real-world problems. Much of the contemporary undergraduate mathematics curriculum in the United States of America focuses on training students to use mathematics that is based on a Cartesian coordinate system. For many professionals in academics, the course they had in pre-collegiate Euclidean geometry is the last exposure they have had to a branch of mathematics that is not necessarily coordinatized. One way to look at mathematical systems is to view them with, and without, Cartesian coordinate systems. Coordinate-based mathematical models are abundant in geography. Far more unusual are research papers that employ a coordinate-free approach: perhaps a reflection of early training of the scholar and the style of interest that grows from that initial nurturing process.
We remember H. S. M. Coxeter, the geometer, characterizing this sort of difference as one of analysis and synthesis. Analytic geometry offers a scheme for breaking a system into basic parts, often using Cartesian coordinates. When the model is moved, the coordinates change—any fundamental structural elements that remain, such as connectivity, are not directly captured by the coordinate system. It is the model itself, rather than the motion that carries it through time or space, which is of interest. Synthetic geometry offers approaches that focus on the idea of transformation. When the model is moved, the transformation is studied with an eye to understanding what remains invariant under that transformation and what is altered by it. Structural elements are often directly captured in the transformational, or synthetic, approach.
Advanced "pure" (as opposed to "applied") mathematics, in the last half of the twentieth century, also takes this approach—that of looking at transformations of various sorts. These transformations might be one-to-one mappings of one set to another, they might be isomorphisms or homomorphisms sending one group to another, they might be homeomorphisms transforming one topological space to another, or they might be any of a number of other possibilities. The world of contemporary pure mathematics is a broad, largely untapped, realm in which to find real-world applications. Graph theory is an ideal launching pad leading to this realm: its basic objects are easy to understand from an intuitive viewpoint, yet it employs the logic and rigor that is characteristic of contemporary pure mathematics.
Professionals in fields other than mathematics often prefer to see problems (synthetic or analytic) in context, and they find the abstract discussions of these problems by mathematicians too obscure. For this reason, we have chosen to take a different approach in this volume. The necessary collection of relevant definitions and theorems is presented here in an interactive manner. We have provided geographic examples from Los Angeles to Berlin and from freeways to pneumatic tube networks, not only to show the synthetic nature of geography as well as of graph theory but also to build the reader's interest so that new applications will ensue. We hope that the manner of presentation, as well as the actual content, will pique the interest of a wide range of readers living in this vibrant world of the second millennium.
In order to make definitions and theorems come to life, we have chosen to apply them in a series of real-world situations. There we look at the problems involved and bring the relevant graph-theoretical model into play. We try to reference the theory as we use it, so that the reader can jump right into these problems immediately and return for more detail, using the interactive look-up feature, when it would provide extra insight. The reader who finds this material stimulating will no doubt enjoy reading the many fine earlier applications of graph theory in geography. To that end, we have provided a bibliography containing direct citations linked to the text and also containing related works of the many who have gone before us and to whom we did not refer directly in this volume. To them and many others we owe heartfelt appreciation and gratitude for their wisdom and research efforts that involve linking mathematics and geography.
We wish to thank our colleague in Anthropology, Professor Per Hage (University of Utah), for his encouragement in this continuing collaborative venture of ours. His constructive commentary, at both the general and specific level, on preliminary material is greatly appreciated. We also thank the reviewers to whom John Wiley & Sons, Inc. sent the manuscript for prepublication review; we gained much useful advice from them and are appreciative of their time, effort, and thoughtfulness.
Colleagues, students, and professional friends alike have supplied inspiration and information in varying amount throughout the years. For their contributions we also thank: Martin Gardner, David Singmaster, Robin Saha, Marc Schlossberg and Professors David Bindschadler, Frank Boesch, Chan-Jin Chung, William D. Drake, Frederick L. Goodman, E. Keith Lloyd, John D. Nystuen, and James R. O’Neil. For computing support, we thank Community Systems Foundation of Ann Arbor (William D. Drake, President). For support with computing and with acquisition of Chicago newspaper articles, we thank Professor Donald F. and Alma S. Lach of Chicago. To all of these individuals, for their helpful thoughts and actions, we offer greatest thanks; errors that remain are, of course, ours alone.
In addition, we wish to honor the memory of Dr. Geert Prins, Professor of Mathematics at Wayne State University. Prins brought us all together: Geert was Harary's Ph.D. student number 2. He was also the Ph.D. advisor of W. C. Arlinghaus and the general advisor of S. L. Arlinghaus. Prins set up a first meeting between Harary and W. C. Arlinghaus that set the latter on his way to work on automorphism groups of graphs. Prins, a great fan of the arts of all sorts, would no doubt have enjoyed knowing that a paper that he and Harary wrote served as the base for the some of the mathematics in an Oscar-winning movie (Good Will Hunting, 1997, Miramax Films) according to an article in the Notices of the American Mathematical Society. We hope he would also have enjoyed seeing this extension of mathematics into the dynamic world of the web.
Finally, we are thankful for the insightful commentary and continuing help from our editor, Steven Quigley, Executive Editor, and the staff of our publisher, John Wiley & Sons, Inc., particularly Heather Haselkorn, Editorial Program Coordinator, Perry King, Web Development Manager, and Andrew Prince, Managing Editor. We also thank Marketing Manager, Fred Filler (with work on marketing copy from Reeves Hamilton) at John Wiley & Sons, Inc. Their wisdom and patience with this new effort in publishing underscore the importance of having a publisher with a long-standing fine reputation at the base of innovative electronic, as well as conventional, publishing.
Sandra Lach Arlinghaus, Ann Arbor, MI
William C. Arlinghaus, Ann Arbor, MI
Frank Harary, Las Cruces, NM
Software used in document creation, all company names
and products should be presumed to carry registered trademarks, patents, or
copyrights:
Hardware used: Hewlett-Packard 800MHz Pentium III, with 40 Mb hard drive and 128 Mb RAM.
Olympus D-400 Zoom 1.3 Megapixel digital camera.
Hewlett-Packard ScanJet.
Base maps cite credits in the figure captions.
Copyright permissions from:
Cambridge University
Press
Generations Press
Geographical Review, American Geographical Society of New York
David Mark
Institute of Mathematical Geography
Metropolitan Transportation Authority, State of New York, NYCTA.
Bruce G. Moffat