Seven Bridges of Königsberg - Wikipedia, the free encyclopedia

Description

The title of this article contains the character ö . Where it is unavailable, the name may be represented as Seven Bridges of Koenigsberg .

The Seven Bridges of Königsberg is a famous historical problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and presaged the idea of topology .

Contents

The city of Königsberg in Prussia (now Kaliningrad , Russia ) was set on both sides of the Pregel River , and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk halfway onto the bridge and then turn around to come at it from another side).

Euler proved that the problem has no solution.

To start with, Euler pointed out that the choice of route inside each landmass is irrelevant. The only important feature of a route is the sequence of bridges crossed. This allowed him to reformulate the problem in abstract terms (laying the foundations of graph theory ), eliminating all features except the list of landmasses and the bridges connecting them. In modern terms, one replaces each landmass with an abstract " vertex " or node, and each bridge with an abstract connection, an " edge ", which only serves to record which pair of vertices (landmasses) is connected by that bridge. The resulting mathematical structure is called a graph .

→ →

Since only the connection information is relevant, the shape of pictorial representations of a graph may be distorted in any way without changing ...

Original URL

http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg