Konigsberg Bridge Problem

Konigsberg Bridge Problem:-  

                               In the eighteenth century good citizens of Konigsberg, capital of 

Eastern Prussia (  now renamed kalningrad and in West Soviet Russia ) would amuse

themselves with the following puzzle. Through the city flowed the lovely river Pregel,

formed two islands C, D ( C is kneiphof island  ) were connected to each other and to

the banks A and B with seven

Bridges (known as Green, merchant’s, Blacksmith’s High, wooden, connecting and Hone as shown in fig. (a).

                          The problem was to start at any of the four land areas of city, A, B, C or D, walk  over  each  of  the  seven  bridges exactly once, and return to the starting point (without swimming across the river, of course).

                             Eular represented this situation by means of a graph as shown in fig (b).the vertices represent the land areas and the edges represent the bridges.

                             No one solved the problem, and so no surprise when the great Swiss mathematician Leonhard Euler (1707 – 1783 ) prove it to be impossible. Eular in 1736, Solved  the  long  standing  bridge problem and wrote the first paper in graph-theory in Latin ( “Solution of a  problem relating to the geometry of positive “) and become the father of graph theory.

                          The Konigsberg bridge problem is the same as the problem of drawing  Fig 10 (b) Without  lifting  the  pen  from the paper and without retracing a line (edge ), and finally reach to the  starting point . Eular proved that this is  possible  only if every point is incident with an even no of lines i.e. every vertex is even . This condition does not hold for the system in fig. (b) where none of the points (vertices) obeys it. Hence the desire tour Cannot be found.in the graph of fig (b) every vertex is odd.

                            Konigsberg Bridge Problem also stated as :- “Is it possible to cross the seven bridges in a continuous walk without recrossing any of them ? “.

                             It can be shown that there is a  path  that  traverses  such  a  network without  crossing Any  segment more than once iff there are fewer than  3 odd  vertices.  [ fig (a) is also not Traceable on a paper without lifting the pen and without retracting a line ].

                         Sadly, the historical city of Konogsberg was completely destroyed in a bombing  raid  during  the  second  world  war The  city  is  now  a naval base  called Kaliningrad  located  in  West  Soviet  Russia . The river Pregel has been renamed the Pregolya and seven bridges are no longer there.