Seven Bridges of Königsberg - AbsoluteAstronomy.com

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler

Leonhard Euler

Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...

in 1735 laid the foundations of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

and prefigured the idea of topology

Topology

Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...

.

The city of Königsberg

Königsberg

Königsberg was the capital of East Prussia from the Late Middle Ages until 1945 as well as the northernmost and easternmost German city with 286,666 inhabitants . Due to the multicultural society in and around the city, there are several local names for it...

in Prussia

Kingdom of Prussia

The Kingdom of Prussia was a German kingdom from 1701 to 1918. Until the defeat of Germany in World War I, it comprised almost two-thirds of the area of the German Empire...

(now Kaliningrad

Kaliningrad

Kaliningrad is a seaport and the administrative center of Kaliningrad Oblast, the Russian exclave between Poland and Lithuania on the Baltic Sea...

, Russia

Russia

Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...

) was set on both sides of the Pregel River

Pregolya

The Pregolya or Pregola is a river in the Russian Kaliningrad Oblast exclave.It starts as a confluence of the Instruch and the Angrapa and drains into the Baltic Sea through Vistula Lagoon. Its length under the name of Pregolya is 123 km, 292 km including the Angrapa. The basin has an...

, 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 and later cross the other half from the other side. Euler proved that the problem has no solution. There could be no non-retracing continuous curve that passed through all seven of the bridges. The difficulty was the development of a technique of analysis and of subsequent tests that established this assertion with mathematical rigor.

Euler's analysis

First, Euler pointed out that the choice of route inside each land mass 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

Graph theory

), eliminating all features except the list of land masses and the bridges connecting them. In modern terms, one replaces each land mass with an abstract "vertex" or node, and each bridge with an abstract connection, an "edge", which only serves to record which pair of vertices (land masses) 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 the graph itself. Only the existence (or absence) of an edge between each pair of nodes is significant. For example, it does not matter whether the edges drawn are straight or curved, or whether one node is to the left or right of another.

Next, Euler observed that (except at the endpoints of the walk), whenever one enters a vertex by a bridge, one leaves the vertex by a bridge. In other words, during any walk in the graph, the number of times one enters a non-terminal vertex equals the number of times one leaves it. Now, if every bridge has been traversed exactly once, it follows that, for each land mass (except possibly for the ones chosen for the start and finish), the number of bridges touching that land mass must be even (half of them, in the particular traversal, will be traversed "toward" the landmass; the other half, "away" from it). However, all four of the land masses in the original problem are touched by an odd number of bridges (one is touched by 5 bridges, and each of the other three is touched by 3). Since, at most, two land masses can serve as the endpoints of a putative walk, the proposition of a walk traversing each bridge once leads to a contradiction.

In modern language, Euler shows that the possibility of a walk through a graph, traversing each edge exactly once, depends on the degrees of the nodes. The degree of a node is the number of edges touching it. Euler's argument shows that a necessary condition for the walk of the desired form is that the graph be connected and have exactly zero or two nodes of odd degree. This condition turns out also to be sufficient—a result stated by Euler and later proven by Carl Hierholzer

Carl Hierholzer

Carl Hierholzer was a German mathematician.-Biography:Hierholzer studied mathematics in Karlsruhe, and he got his Ph.D. from Ruprecht-Karls-Universität Heidelberg in 1865. His Ph.D. advisor was Ludwig Otto Hesse...

. Such a walk is now called an Eulerian path
Eulerian path
In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is a Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of...

(oy•lɛr•i•ən) or Euler walk in his honor. Further, if there are nodes of odd degree, then any Eulerian path will start at one of them and end at the other. Since the graph corresponding to historical Königsberg has four nodes of odd degree, it cannot have an Eulerian path.

An alternative form of the problem asks for a path that traverses all bridges and also has the same starting and ending point. Such a walk is called an Eulerian circuit or an Euler tour. Such a circuit exists if, and only if, the graph is connected, and there are no nodes of odd degree at all. All Eulerian circuits are also Eulerian paths, but not all Eulerian paths are Eulerian circuits.

Euler's work was presented to the St. Petersburg Academy on August 26, 1735, and published as Solutio problematis ad geometriam situs pertinentis (The solution of a problem relating to the geometry of position) in the journal Commentarii academiae scientiarum Petropolitanae in 1741. It is available in English in The World of Mathematics.

Significance in the history of mathematics

In the history of mathematics

History of mathematics

The area of study known as the history of mathematics is primarily an investigation into the origin of discoveries in mathematics and, to a lesser extent, an investigation into the mathematical methods and notation of the past....

, Euler's solution of the Königsberg bridge problem is considered to be the first theorem of graph theory

Graph theory

, a subject now generally regarded as a branch of combinatorics

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

. Combinatorial problems of other types had been considered since antiquity.

In addition, Euler's recognition that the key information was the number of bridges and the list of their endpoints (rather than their exact positions) presaged the development of topology

Topology

. The difference between the actual layout and the graph schematic is a good example of the idea that topology is not concerned with the rigid shape of objects.

Variations

The classic statement of the problem, given above, uses unidentified nodes—that is, they are all alike except for the way in which they are connected. There is a variation in which the nodes are identified—each node is given a unique name or color.

The northern bank of the river is occupied by the Schloß, or castle, of the Blue Prince; the southern by that of the Red Prince. The east bank is home to the Bishop's Kirche, or church; and on the small island in the center is a Gasthaus
Gasthaus
A Gasthaus is a German-style inn or tavern with a bar, a restaurant, banquet facilities and hotel rooms for rent.Gasthäuser are typically found in smaller towns and are often family-owned...

, or inn.

It is understood that the problems to follow should be taken in order, and begin with a statement of the original problem:

It being customary among the townsmen, after some hours in the Gasthaus, to attempt to walk the bridges, many have returned for more refreshment claiming success. However, none have been able to repeat the feat by the light of day.

8: The Blue Prince, having analyzed the town's bridge system by means of graph theory, concludes that the bridges cannot be walked. He contrives a stealthy plan to build an eighth bridge so that he can begin in the evening at his Schloß, walk the bridges, and end at the Gasthaus to brag of his victory. Of course, he wants the Red Prince to be unable to duplicate the feat from the Red Castle. Where does the Blue Prince build the eighth bridge?

9: The Red Prince, infuriated by his brother's Gordian

Gordian Knot

The Gordian Knot is a legend of Phrygian Gordium associated with Alexander the Great. It is often used as a metaphor for an intractable problem solved by a bold stroke :"Turn him to any cause of policy,...

solution to the problem, wants to build a ninth bridge, enabling him to begin at his Schloß, walk the bridges, and end at the Gasthaus to rub dirt in his brother's face. As an extra bit of revenge, his brother should then no longer be able to walk the bridges starting and ending at his Schloss as before. Where does the Red Prince build the ninth bridge?

10: The Bishop has watched this furious bridge-building with dismay. It upsets the town's Weltanschauung
World view
A comprehensive world view is the fundamental cognitive orientation of an individual or society encompassing the entirety of the individual or society's knowledge and point-of-view, including natural philosophy; fundamental, existential, and normative postulates; or themes, values, emotions, and...

and, worse, contributes to excessive drunkenness. He wants to build a tenth bridge that allows all the inhabitants to walk the bridges and return to their own beds. Where does the Bishop build the tenth bridge?

Solutions

Reduce the city, as before, to a graph. Color each node. As in the classic problem, no Euler walk is possible; coloring does not affect this. All four nodes have an odd number of edges.

8: Euler walks are possible if exactly zero or two nodes have an odd number of edges. If we have 2 nodes with an odd number of edges, the walk must begin at one such node and end at the other. Since there are only 4 nodes in the puzzle, the solution is simple. The walk desired must begin at the blue node and end at the orange node. Thus, a new edge is drawn between the other two nodes. Since they each formerly had an odd number of edges, they must now have an even number of edges, fulfilling all conditions. This is a change in parity

Even and odd numbers

In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...

from an odd to even degree.

9: The 9th bridge is easy once the 8th is solved. The desire is to enable the red castle and forbid the blue castle as a starting point; the orange node remains the end of the walk and the white node is unaffected. To change the parity of both red and blue nodes, draw a new edge between them.

10: The 10th bridge takes us in a slightly different direction. The Bishop wishes every citizen to return to his starting point. This is an Euler circuit and requires that all nodes be of even degree. After the solution of the 9th bridge, the red and the orange nodes have odd degree, so their parity must be changed by adding a new edge between them.

Present state of the bridges

Two of the seven original bridges were destroyed during the bombing of Königsberg in World War II

Bombing of Königsberg in World War II

The bombing of Königsberg was a series of attacks made on the city of Königsberg in East Prussia during the World War II. The Soviet Air Force had made several raids on the city since 1941. Extensive attacks carried by RAF Bomber Command destroyed most of the city's historic quarters in the...

. Two others were later demolished and replaced by a modern highway. The three other bridges remain, although only two of them are from Euler's time (one was rebuilt in 1935). Thus, , there are now five bridges in Kaliningrad.

In terms of graph theory, two of the nodes now have degree 2, and the other two have degree 3. Therefore, an Eulerian path is now possible, but since it must begin on one island and end on the other, it is impractical for tourists.

At Canterbury University, in Christchurch

Christchurch

Christchurch is the largest city in the South Island of New Zealand, and the country's second-largest urban area after Auckland. It lies one third of the way down the South Island's east coast, just north of Banks Peninsula which itself, since 2006, lies within the formal limits of...

, New Zealand

New Zealand

New Zealand is an island country in the south-western Pacific Ocean comprising two main landmasses and numerous smaller islands. The country is situated some east of Australia across the Tasman Sea, and roughly south of the Pacific island nations of New Caledonia, Fiji, and Tonga...

, a model of the bridges is incorporated in a grass area between the old Physical Sciences Library and the Erskine Building, housing the Departments of Mathematics, Statistics and Computer Science.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Euler's analysis

Significance in the history of mathematics

Variations

Solutions

Present state of the bridges

See also

External links