Definition
In Geographic Information Systems, concepts from graph theory are extremely useful in expressing the spatial structure of entities seen as points, lines, areas and solids, after the geometrical details of these entities are removed. For example, in transportation and river networks, the topological properties of their structures can be represented using graphs. This article describes the origins of graph theory and the impact it has on various fields ranging from geography to economics.
The Konigsberg Bridge Problem is a classic problem, based on the topography of the city of Konigsberg, formerly in Germany but now known as Kalingrad and part of Russia. The river Pregel divides the city into two islands and two banks as shown in Fig. 1. The city had seven bridges connecting the mainland and the islands (represented by thick lines in the figure). (Chartrand 1985; Harary...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Biggs NL, Lloyd EK, Wilson RJ (1976) Graph theory 1736–1936. Oxford University Press, Oxford
Biggs NL, Lloyd EK, Wilson RJ (1998) Graph theory. Oxford University Press, Oxford
Bollobás B (1979) Graph theory: an introductory course, p 12. Springer, Berlin
Chartrand G (1985) The Königsberg bridge problem: an introduction to Eulerian graphs. In: Introductory graph theory. Dover, New York
Christofides N (1973) The optimum traversal of a graph. Int J Manage Sci 1(6):719–732
Edmonds J, Johnson EL (1973) Matching, Euler tours and Chinese postman. Math Program 5:88–124
Evans JR, Minieka E (1992) Optimization algorithms for networks and graphs. Marcel Dekker Inc., New York
Fleischner H (2001) (Some of) the many uses of Eulerian graphs in graph theory. Discret Math 230:23–43
Harary F (1994) Graph theory, pp 1–2. Addison-Wesley, Reading
Hartsfield R (1990) Pearls in graph theory. Academic, San Diego
Shekhar S, Chawla S (2003) Spatial databases: a tour. Prentice Hall, Upper Saddle River
Steinhaus H (1999) Mathematical snapshots, 3rd edn. Dover, New York, pp 256–259
Wilson RJ (1985) Introduction to graph theory. Longman Inc., New York
Wilson RJ, Beineke LW (eds) (1979) Applications of graph theory. Academic, London/New York
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this entry
Cite this entry
George, B. (2017). Graph Theory, Konigsberg Problem. In: Shekhar, S., Xiong, H., Zhou, X. (eds) Encyclopedia of GIS. Springer, Cham. https://doi.org/10.1007/978-3-319-17885-1_547
Download citation
DOI: https://doi.org/10.1007/978-3-319-17885-1_547
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17884-4
Online ISBN: 978-3-319-17885-1
eBook Packages: Computer ScienceReference Module Computer Science and Engineering