Puzzles/Seven Bridges of Königsberg
Seven Bridges of Königsberg
editIn the early 18th century, there was a city called Königsberg (Kaliningrad, as it is now called) which was an old Prussian city (previously an enclave of Germany, but now part of Russia) on the banks of the Pregel River. The city layout itself is unique as the island of Kneiphof (Kant Island, as it is now called) is surrounded, with two central landmasses connected by 7 bridges (See pic 1) during the olden times as shown below.
According to the story, that seven bridges were called Blacksmith’s bridge, Connecting Bridge, Green Bridge, Merchant’s Bridge, Wooden Bridge, High Bridge, and Honey Bridge.
The citizens of Königsberg used to spend Sunday afternoons walking around their beautiful city. While walking, the people of the city decided to create a game for themselves, their goal being to devise a way in which they could walk around the city, crossing each of the seven bridges only once in one walk around the city. Even though none of the citizens of Königsberg could invent a route that would allow them to cross each of the bridges only once, still they could not prove that it was impossible.
Unfortunately, in the case of Königsberg, all did not end that well. When Prussia dissolved, Königsberg eventually became a part of Russia ( the city has since been renamed Kaliningrad since then). Two of the original bridges were bombed by Allies in 1942, during WWII and rebuilt after the war. Two other bridges were later demolished to make room for a highway. Now, as of in 21st century, it is possible to complete the tour around the city in one walk with the five remaining bridges.
Leonhard Euler & Euler Path
editLeonhard Euler (See pic 2), a Swiss mathematician, were intrigued by this particular problem and as of that time; neither the geometry, nor algebra, nor even the art of counting was sufficient to solve it.
On August 1735, Euler publish paper titled of "Solutio problematis ad geometriam situs pertinentis" .
In this paper Paragraph 1, Euler states that he believes this problem concerns geometry, but not the geometry well known by his contemporaries, that involves measurements and calculations, but instead a new kind of Geometry, which referred to as Geometry of Position.
He pointed out that the choice of route inside each land mass does not matter. The only important property of a route is the order in which the bridges are crossed. So, he changed the problem to abstract terms. Euler provided a sketch of the problem and removed all features of the maps except the list of land masses (which he labelled A,B,C,D) and the bridges (a,b,c,d,e,f,g) connecting them. (See pic 3)He states the general question of the problem, “Can one find out whether or not it is possible to cross each bridge exactly once?”
In Paragraph 3, Euler tells the reader that to solve this specific problem, he could write down all possible paths, but this technique would take a great deal of time, and would not work for larger configurations with more bridges and land masses. Because of these issues, Euler decided to choose a different method for solving this problem.
In both paragraph 4 and 5, Euler begins simplifying the problem and replaced each land mass with an abstract "vertex" or node. Then he replaced each bridge with an abstract connection, an "edge". An edge (road) recorded which two vertices (land masses) were connected. In this way, he formed a graph. Each crossing shall be labelled as follow: If the crossing taken from landmass A to landmass B, it will be known as AB. (See pic 4)
In Paragraph 5, Euler continues his discussion on this process explaining that in ABDC, although there are four capital letters, only three bridges were crossed. Euler explains that no matter how many how many bridges there are, there will be one more letter to represent the necessary crossing. Because of this, the whole of the Königsberg Bridge problem required seven bridges to be crossed, and therefore in actuality, required eight bridges for crossing.
In conclusions, Euler states that, “In general, if the number of bridges is any odd number, and if it is increased by one, then the number of occurrences of A is half of the result.” Which meant that, every bridge has two ends, and every bridge end lies in other land masses. Therefore, the number of bridge ends equals twice the number of bridges, and is always an even number. When we count the number of bridge connections in a region, we’re counting bridge ends. So if some region has an odd number of connections, there must also be another region with an odd number, because the sum of all the bridge ends must be even.
Gallery
edit-
Pic 1: Map of old Konigsberg with rivers and bridges colorised -
Pic 2: Portrait of Leonhard Euler -
Pic 3: Leonhard Euler Sketches on Konigsberg bridge -
Pic 4: Simplifications of 7 bridges of Konigsberg bridge
.png){kind=small}