KONIGSBERG BRIDGE PROBLEM

-
Konigdberg bridge problem ( Real life mathematical problem )

Konigsberg is a town on the Pregel River, which in the 18th century was a German town, but now is Russia. 

 The problem led to the development of the branches of mathematics known as Topology and Graph Theory.

 The problem of bridge is as follows:

  • Within the town are two river islands that are connected to the banks with seven bridges as shown.
  • People tried to walk around the town in a way that only crossed each bridge once,but it proved to be difficult problem. 
  • Leonhard Euler, a Swiss mathematician in the service of the Russian empire Catherine the Great, heard about the problem.
  • In 1736 Euler proved that the walk was not possible to do. He proved this by inventing a kind of diagram called a network, that is made up of vertices  ( dots where lines meet ) and arcs ( lines ).
He used four dots ( vertices ) for the two river banks and the two islands.These have been marked A, B and C, D. The seven lines ( arcs ) are the seven bridges.
  • 3 bridges join to river bank A.
  • 3 bridges join to river bank B.
  • 5 bridges join to island C.
  • 3 bridges join to island D.

What information do you get from the above four lines? All the vertices have an odd number of arcs, so they are called odd vertices.

  • The problem was to travel around town crossing each bridge only once. On Euler's network this meant tracing over each arc once, visiting all the vertices.
  • Euler proved it could not be done because he worked out that , to have an odd vertex you would have to begin or end the trip at that vertex.
  • Since there can only be one beginning and one end, there can only be two odd vertices if you are to trace over each arc only once.
  • Since the bridge problem has 4 odd vertices, it just not possible to do! See the figure.

 After Euler proved his theorem, much water has flown under the bridges in Kinigsberg. An extra bridge was built in 1875, joining the land areas of river banks A and B.

 Is it possible now for the Konigsbergians to go around the city using each bridge once?

 Here is the situation as you can see in the figure. After the addition of the new bridge , both the vertices A and B have become even degree vertices .

 So, it is possible for the Konigsbergians to go around the city using each bridge exactly once. 

Comments

Post a Comment

Popular posts from this blog

DOT PUZZLE ( CONNECT ALL THE DOTS WITHOUT LIFTING THE PEN AND WITH ONLY FOUR STRAIGHT LINES WITHOUT ANY OVERLAP )

-
Image
Here we would solve a dot puzzle Consider the figure below Connect all the dots without lifting the pen with only 4 straight lines and the lines do not overlap. Here are some examples already done for you but not been solved because some dots left to be crossed. You could see that some dots have been left to be crossed by the line. So do you think you could solve it. Let us try one more time. Now, what do you see, the puzzle has been solved with the required conditions. Find out some more solutions to this question.
Read more

EULER TRAIL PUZZLE

-
Image
What is an Euler trail ? An Euler trail ( Euler path ) is a trail in a finite graph which visits every edge exactly once. An Euler trail is a walk on the edges of a graph which uses each edge exactly once. Euler trail is also called an Euler chain , Euler walk , Euler path . Here is the puzzle as you could see in the picture. Your job is to cross each line exactly once without lifting your pen.  In the following figure consider every marked line as a single line and each must be crossed once without lifting you pen. Here are some examples already done, but in each case, one line is left ( marked red ) to be crossed . See the figures. Have you got the solution ? well, this is impossible to do however hard you try.  Explanation Consider the figure below and find the numbers of line reaching the centre of each box. In the figure you could see that there are three centre points with odd number o...
Read more