Geography Reference
In-Depth Information
residents of Königsberg (now Kaliningrad). The puzzle sought a solution about
how to cross seven bridges that connected two islands in the middle of the city
without crossing any bridge twice.
Euler's solution was to abstract the problem into a set of relationships
between vertices (also called nodes), edges, and faces. This is called a graph.
Euler established that a graph has a path traversing each edge exactly once if
exactly two vertices link an odd number of edges. Since this isn't the case in
Königsberg there isn't a route that crosses each bridge once and only once.
Figure showing Euler's seven bridges of Königsberg problem.
The mathematics of this relationship are simple. To determine if there is
single relationship, count the number of vertices connecting three edges. If the
number of vertices is two, then there is a single way around. Otherwise, at least
one vertice must be crossed twice.
Euler contributed an immense body of work, over 775 papers, half of
which were written after he went blind at the age of 59. The Königsberg prob-
lem is related to Euler's polyhedral formula, which is the basis for determining
topology in a GIS:
v
-
f
+
e
=2
v
stands for the number of vertices,
f
for the number of faces, and
e
for
the number of edges. Regardless of the type of polygon, this number will
always be two.
Topology was extended by numerous mathematicians in the late 19th cen-
tury, and although most people learn little about it, it has been immensely sig-
nificant for many technological developments.
Topology focuses on connectivity. In regards to GIS, topology is impor-
tant for three reasons. First, it can be calculated to determine if all polygons
are closed, lines connected by nodes, and nodes connected to lines. This allows
for the determination of errors in digitized or scanned vector data. Second, it
can be used in network GI to determine network routing. Finally, because it
allows that the same line (edge) is used for neighboring polygons, the number
of lines stored in a GIS can be greatly reduced.
Review Questions
1. What sets GI apart from maps in terms of discrete and nondiscrete
information?
2. Why are multiple types of data structures needed?
3. What is Tobler's transformational concept?
Search WWH ::
Custom Search