FACTOID # 5: Minnesota and Connecticut are both in the top 5 in saving money and total tax burden per capita.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Seven Bridges of Königsberg
Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges.
Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges.

The Seven Bridges of Königsberg is a problem inspired by an actual place and situation. The city of Königsberg, Prussia (now Kaliningrad, Russia) is set on the river Pregel, and included two large islands which were connected to each other and the mainland by seven bridges. The question is whether it is possible to walk with a route that crosses each bridge exactly once, and return to the starting point. In 1736, Leonhard Euler proved that it was not possible. Locator map on an international level map of Kaliningrad Oblast Kaliningrad (Russian: Калининград), seaport city, capital and main city of the Kaliningrad Oblast, a small Russian exclave between Poland and Lithuania with access to the Baltic Sea. ... Pregolya (Преголя), also spelt as Pregola (German: Pregel) is a river in the Russian exclave of Kaliningrad. ... Events January 26 - Stanislaus I of Poland abdicates his throne. ... Leonhard Euler aged 49 (oil painting by Emanuel Handmann, 1756) Leonhard Euler (April 15, 1707 - September 18, 1783) (pronounced oiler) was a Swiss mathematician and physicist. ...


Circa 1750, the prosperous and educated townspeople allegedly walked about on Sundays trying to solve the problem, but this might be an urban legend. Events March 2 - Small earthquake in London April 4 - Small earthquake in Warrington, England August 23 - Small earthquake in Spalding, England September 30 - Small earthquake in Northampton, England November 16 – Westminster Bridge officially opened Jonas Hanway is the first Englishman to use an umbrella James Gray reveals her sex to... Urban Legend is also the name of a 1998 movie. ...

Contents

Euler's solution

In proving the result, Euler formulated the problem in terms of graph theory, by abstracting the case of Königsberg -- first, by eliminating all features except the landmasses and the bridges connecting them; second, by replacing each landmass with a dot, called a vertex or node, and each bridge with a line, called an edge or link. In mathematics and computer science, graph theory studies the properties of graphs. ... In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ... The term node can refer to: Node, a spatial locus along a standing wave where the wave has minimal amplitude. ... Enhanced Data Rates for GSM Evolution (EDGE) is a digital mobile phone technology which acts as a bolt-on enhancement to 2G and 2. ... The term link can refer to: Look up Link in Wiktionary, the free dictionary A connection between two objects, or an element of a chain. ...


→ → Abstract graph corresponding to bridges of Konigsburg. ...


Note that graph theory is a branch of topology. The shape of a graph may be distorted in any way, so long as the links between nodes are unchanged. It does not matter whether the links are straight or curved, or whether one node is to the left of another. Topology (Greek topos = place and logos = word) is a branch of mathematics concerned with the study of topological spaces. ...


Euler showed that a circuit of the desired form is possible if and only if there are no nodes (dots in the picture of the graph) that have an odd number of edges touching them. Such a walk is called an Eulerian circuit or an Euler tour. Since the graph corresponding to Königsberg has four such nodes, the path is impossible. The Königsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ...


If the starting point does not need to coincide with the end point there can be either zero or two nodes that have an odd number of edges touching them. Such a walk is called an Eulerian trail or Euler walk. So this too was impossible for the seven bridges of Königsberg. The Königsberg Bridges graph In the mathematical field of graph theory, an Eulerian path is a path in a graph which visits each edge exactly once. ...


Significance in the history of mathematics

In the history of mathematics, it is one of the first problems in graph theory to be formally discussed, and also, as graph theory can be seen as a part of topology, one of the first problems in topology. (The field of combinatorics also has a claim on graph theory, but combinatorial problems had been considered much earlier.) See Timeline of mathematics for a timeline of events in mathematics. ... In mathematics and computer science, graph theory studies the properties of graphs. ... Topology (Greek topos = place and logos = word) is a branch of mathematics concerned with the study of topological spaces. ... Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria, and is in particular concerned with counting the objects in those collections (enumerative combinatorics) and with deciding whether certain optimal objects exist (extremal combinatorics). ...


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 and/or color.

The northern bank of the river is occupied by the Schloß, or castle, of the Blue Prince; the southern by 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, or inn.


It is understood that the problems are taken in chronological 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, and many have returned for more refreshment claiming success. However, none have been able to repeat the feat by the light of day.


The Blue Prince's 8th bridge

The Blue Prince, having analyzed the town's bridge system by means of graph theory, concludes the bridges cannot be walked. He contrives a stealthy plan to build an 8th 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, the Blue Prince is unable to duplicate the feat.

  • Where does the Blue Prince build the 8th bridge?

The Red Prince's 9th bridge

The Red Prince, infuriated by his brother's Gordian solution to the problem, builds a 9th bridge, enabling him to begin at his Schloß, walk the bridges, and end at the Gasthaus to rub dirt in his brother's face. His brother can then no longer walk the bridges himself. Alexander cuts the Gordian Knot, by Jean-Simon Berthélemy ((1743—1811) The Gordian Knot is a metaphor for an intractable problem, solved by a bold stroke (cutting the Gordian knot). The myth it refers to is associated in legend with Alexander the Great. ...

  • Where does the Red Prince build the 9th bridge?

The Bishop's 10th bridge

The Bishop has watched this furious bridge-building with dismay. It upsets the town's Weltanschauung and, worse, contributes to excessive drunkenness. He builds a 10th that allows all the inhabitants to walk the bridges and return to their own beds.

  • Where does the Bishop build the 10th bridge?

Solutions

Solutions to these variant problems are given here.


See also


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m