Königsberg bridge problem

from Wikipedia, the free encyclopedia

The Seven Bridges of Königsberg is a mathematical question of the early 18th century, based on the seven Konigsberg Pregelbrücken was illustrated. In graph theory it corresponds to the Euler cycle problem .

Bridge connections

Königsberg is divided by the Pregel and its two islands. The two halves of the city were connected to the islands by three bridges each, which were connected to each other by another bridge.

Konigsberg bridges.png→ 7 bridges.svg→ Königsberg graph.svg

Question

The question was whether there is a path where you cross all seven bridges exactly once, and if so, whether a circular path is also possible, where you get back to the starting point.

Leonhard Euler proved in 1736 that such a path or "Eulerscher Weg" was not possible in Königsberg, as an uneven number of bridges led to all four bank areas or islands. There should be a maximum of two banks (nodes) with an odd number of connected bridges (edges). These two banks could be the starting point or the end point. The remaining banks would have to have an even number of bridges in order to be able to leave them again on a new path.

The bridge problem is not a classic geometrical problem, as it does not depend on the precise location of the bridges, but only on which bridge connects which islands. It is therefore a topological problem that Euler solved using methods that are now included in graph theory . The problem can be generalized to any graph and to the question of whether there is a cycle in it that uses all edges exactly once. Such a cycle is called an Euler's circle and a graph that has an Euler's circle is called an Eulerian. The question of whether a graph is Eulerian can be answered relatively easily and is also possible in directed graphs and graphs with multiple edges .

Due to the effects of the war and renovations after 1945, the original situation in today's Kaliningrad no longer exists. Two of the bridges leading to the island of Kneiphof no longer exist; on the north and south banks only two instead of three bridges each end. Now an Euler path is possible, but still no Euler circle.

literature

  • Gustav Theodor Hoffheinz: The seven bridges in Königsberg . Old Prussian monthly, NF 18 (1881), p. 282 ff.
  • Wladimir Velminski: Leonhard Euler. The birth of graph theory . Kulturverlag Kadmos, Berlin 2008, ISBN 978-3-86599-056-3 .
  • Rudolf Fritsch , Jewgeni Peregud, Sergei Matsejewski: Selected Chapters of Graph Theory (in Russian), Publishing House of the State Immanuel Kant University, Kaliningrad 2008.

Web links

Commons : Seven Bridges of Königsberg  - Collection of images, videos and audio files