Fig.1Based of what i've read, the konigsberg's bridge problem is a unique case. No wonder Euler wouldbe interested on it. Konigsberg located in a strategic position on the river Pregel, that's whay it become a trading center and an importanr medieval city. the river Pregel also divided this area into four land, which is conected with seven bridge : Blacksmith's bridge, connecting's bridge, High bridge, Green bridge, Honey bridge, merchant's bridge and Wooden bridge. As illustrated on figure 1.
Konigsberg is a city with beautiful scenery, the citizens of konigsberg used to spend their sunday afternoons by walking around their city. i don't know why people always make a trouble for themself. The problem was to find a walk trough the city that would cross each bridge once and only once, and if possible, returning to their start point. None can solved it, but Konigsberg is near with St. Petersburg, where the famous mathematicians Euler stay.
I found on some mathematics books about Euler investigated the Konigsberg's bridge by drawing a graph of the city as the figure below :
Konigsberg is a city with beautiful scenery, the citizens of konigsberg used to spend their sunday afternoons by walking around their city. i don't know why people always make a trouble for themself. The problem was to find a walk trough the city that would cross each bridge once and only once, and if possible, returning to their start point. None can solved it, but Konigsberg is near with St. Petersburg, where the famous mathematicians Euler stay.
I found on some mathematics books about Euler investigated the Konigsberg's bridge by drawing a graph of the city as the figure below :
Fig. 2In 1736, Euler wrote up his solution in the Commentarii Academiae Scientriarum Imperialis Petropolitanae under the title 'Solutio Problematis ad Geometrian situs pertinentis'. Euler's diagram of Konigsberg appears in figure 3 :
Fig.3Altough dated 1736, Euler's paper wasn't actually published until 1741, and was reprented in the new edition on the Commenterii (Novi Acta Commentarii.... ) which is appeared in 1752.
Euler's paper divided into twenty-one numbered paragraph. In his paper, Euler generelized the problem : "Whatever be the arrangement and division of the river into branches, and however many bridges there be, can one find out wheter or possible to cross each bridge exactly once?".
At the first, Euler try to list the possible paths and find the tour which is suitable for Konigsberg's problem. but this method has many weakness, like there so many possible paths, it need a long time and it can't used for more bridges and lands. Hence, Euler decide to look for another method that can find the specific tour with simple step.
Euler use the letter A, B, C, and D to represented the land. If someone walk from A to B right across bridge a or b, the path is AB. A is the initial region and B is the final. In the same way, if someone walk from A to B, B to D and D to C, then the three trips can be represented as ABDC. A is the inital region and C is the final region. Since each land separate by river, this people need to cross 3 bridges. in the same way, if we cross 4 bridges, the path represented with 5 combination letters.
The generalization is, if we cross n bridges the the combination letters is n + 1. The Konigsberg has 7 bridges so the paths can be represented by 8 combination letters.
Euler ignore which bridge is used, as long as the property of initial region and the final region is complete. The Konigsberg's problem can be simplify to look for combination of 8 letters, from A, B, C, and D, and the pair of letters appears with certain frecuency. the region A and B in connected by 2 bridges, so A and B will be used twice, A and C also twice. but, for A and D, B and D, C and D just once.
Before going to the next steps, Euler try to find a formula to indicates wheather possible or not to find the tour. Euler developed the answer from a simpler example on the figure below :
Fig. 4
Euler's paper divided into twenty-one numbered paragraph. In his paper, Euler generelized the problem : "Whatever be the arrangement and division of the river into branches, and however many bridges there be, can one find out wheter or possible to cross each bridge exactly once?".
At the first, Euler try to list the possible paths and find the tour which is suitable for Konigsberg's problem. but this method has many weakness, like there so many possible paths, it need a long time and it can't used for more bridges and lands. Hence, Euler decide to look for another method that can find the specific tour with simple step.
Euler use the letter A, B, C, and D to represented the land. If someone walk from A to B right across bridge a or b, the path is AB. A is the initial region and B is the final. In the same way, if someone walk from A to B, B to D and D to C, then the three trips can be represented as ABDC. A is the inital region and C is the final region. Since each land separate by river, this people need to cross 3 bridges. in the same way, if we cross 4 bridges, the path represented with 5 combination letters.
The generalization is, if we cross n bridges the the combination letters is n + 1. The Konigsberg has 7 bridges so the paths can be represented by 8 combination letters.
Euler ignore which bridge is used, as long as the property of initial region and the final region is complete. The Konigsberg's problem can be simplify to look for combination of 8 letters, from A, B, C, and D, and the pair of letters appears with certain frecuency. the region A and B in connected by 2 bridges, so A and B will be used twice, A and C also twice. but, for A and D, B and D, C and D just once.
Before going to the next steps, Euler try to find a formula to indicates wheather possible or not to find the tour. Euler developed the answer from a simpler example on the figure below :
Fig. 4If A connected with 3 bridges then A will appears twice. If there are five bridges connected to A region, then A will appears 3 times. the generalization is :
if there is an odd number k of bridges, the letter must appear (k + 1 )/2 times.
Since kneiphof is connected by five bridges, the path must contain three As. Similarly. there must be two Bs, two Cs, and two Ds. See the table below:
if there is an odd number k of bridges, the letter must appear (k + 1 )/2 times.
Since kneiphof is connected by five bridges, the path must contain three As. Similarly. there must be two Bs, two Cs, and two Ds. See the table below:
Summing the final row of frequency gives 9 required letters, but Koingsberg has 7 bridges which exactly once can have only 8 letters. Thus there can be no Konigsberg tour.Euler continued his analysis :
if there is an even number k of bridges connecting a land mass, then the corresponding letter appears (k / 2) + 1 times if the path begin in that region, and k /2 times otherwise.
Ok, that's all i know about Konigsberg. Thanks for read.
References :
http://www.gss.ucsb.edu/hopkins1.pdf
http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
http://www.math.nmsu.edu/his_projects/Euler-Barnett.pdf
