Table of Contents
Chapter 1: Geography and Graph Theory
Independent Discoveries of Graph Theory
The Timeless
Euler and Königsberg
The Chinese Postman Problem
Commentary
Hamiliton and the Around-the-World Puzzle
The Timely
Jordan Curve Theorem
Earth Geometry
Projection
Adjacency
--Chapter 1c complementary section
Basic Material
Connectedness: Terminology
Degree and Euler's theorem
Dinner Guests and Ramsey's Theorem
Bipartite Graphs and König's Theorem
Traversability: Eulerian and Hamiltonian Graphs
Chapter 2: The Berlin Rohrpost and Centrality
The Berlin Rohrpost Background
Center of the Rohrpost Tree: An Application of Eccentricity
Centroid
of the Rohrpost Tree: An Application of Branch Weight
Spatial Synthesis
--Chapter 2c complementary section
Trees
Centers and Centroids
Chapter 3: The Parisian Pneumatique and Orientation
The Parisian Pneumatique: Background and Orienation
Connection in the Pneumatique
Orientation: Chiral and Achiral Models
Spatial Synthesis
--Chapter 3c complementary section
Connectedness and Directed Graphs: Terminology
Robbin's One-Way Street Theorem
Network Flows
Chapter 4: Chicago, New York and Connectivity
The Great Chicago Flood: Background
Mapped Evidence from the Press
Evidence from Triangulated
Irregular Networks
Graphic Guidance
Subway of 1942 Causes
Fragmentation of Freight Tunnel Network
Planarity: A Graphical View
The New York City Subway System and Connectivity
Barrier-Free Access between Topographic Layers: The New York Subway System
The Elevator Theorem
The New York City Subway Map
Summary
--Chapter 4c complementary section
Disconnection of Graphs: Some Terminology
Equivalent Conditions for Bridges and Blocks
Menger's Theorem
Max-flow Min-cut Theorem
Chapter 5: The Paris Metro and Planarity
The Paris Metro: One Route from Here to There
Planarity and the Paris Metro
Topographic Signifcance of the Lack Planarity
Detroit Water Distribution Network: A Real-World Application of Kuratowski's Theorem
--Chapter 5c complementary section
Planarity
Kuratowski's Theorem
Chapter 6: Transportation Routes and Network Algorithms
Alternate Routing Analysis: Hasse's Algorithm
Los Angeles, 1994
Pre-eathquake configuration
Post-eathquake configuration
Spanning Trees: Ann Arbor, Michigan, 2000
--Chapter 6c complementary section
Shortest Distance between Nodes in a Graph
Algorithms for Spanning Trees
Minimal Spanning Trees
Kruskal's Algorithm
Prim's Algorithm
Chapter 7: Maps and Four-Color Theorem
Coloring Thematic Maps
Continuity
Color Characterization
Vectors in Color Space
Color Charts and Manhattan Space: Color Ramps and Alternate Metrics
Partition
Adjacency and Coloring
The Mediterranean Basin: Countries Sharing a Common Resource
How Many Colors?
--Chapter 7c complementary section
Chapter 8: Symmetry and Geography: Spatial Transformations
Steiner Trees: A Network Algorithm That Brings in New Nodes
General Discussion
General Context
Steiner Construction for the Triangle
Construction for the Pentagon
Steiner Transformation
Fractal Transformation: Contemporary Interpretations
Cellualar Telephone Towers
Pixel Sequences
--Chapter 8c complementary section
Symmetry and Mathematics: Automorphism Groups of Graphs
Basic Terminology
Isomorphism of Graphs
Groups
Direct Products and a Fundamental Theorem
The Symmetric Group
Automorphism Groups of Graphs
Isomorphism of Graphs
The Regular n-gon
Smallest Graphs with Given Automorphism Group
F-diagrams of Graphs
Smallest Graphs with Given Cyclic Group
Automorphism Groups of Digraphs
Wreath Products and Automorphism
Glossary
Bibliography
Comment about e-Book
Preface
This book is written for the internet.
-
Conventional eBooks take advantage merely of the
Internet's distribution capabilities. This eBook additionally employs
color, animation, and linking capabilities supplied at no extra
publishing cost that are available only on the Internet.
-
Each chapter has a mirror, complementary chapter. Thus, Chapter X has
heavier focus on geography while Chapter Xc (Chapter X
Complement—the “c” is for “complement”) has heavier focus on
the mathematics behind the geography. (The notion of complement
is itself a graph-theoretic term.)
-
The web version offers the reader the opportunity to see animations of or
and to jump back and forth between the two approaches to the same
material.
-
The ordering of the chapters is according to mathematical complexity:
Chapter 1 has the most elementary mathematical base and Chapter 8 has
the most advanced.
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 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
|
