Konigsberg bridge problem (3)

Konigsberg bridge problem

1. KONIGSBERG BRIDGE PROBLEM PRESENTED BY MRS.JISHA M S ASSISTANT PROFESSOR DEPARTMENT OF MATHEMATICS M.S.M COLLEGE ,KAYAMKULAM

2. The Konigsberg Problem Konigsberg was a city in Prussia (now Kaliningrad, Russia) This city was situated in both sides of the Pregel River and included 2 large islands-which were connected to each other, or to the mainland portions of the city, by 7 bridges.

3. The Seven Bridges of Königsberg The old town of Königsberg has seven bridges:

4. PROBLEM : Can you take a walk through the town, visiting each part of the town and crossing each bridge exactly once ?

5. Simplifying it : We can simplify the map above to just this:

6. There are 4 land areas of the town-on the mainland north of the river , on the mainland south of the river and the 2 islands . Let us label them A,B,C, & D. To visit each part of the town you should visit the points A,B,C & D. Let us label the bridges p,q,r,s,t,u & v You should cross each bridge exactly once .

7. LABELED FIGURE

8.   Now we again simplifying this picture by points and curves(or lines) where land areas are indicated by points and bridges are indicated by lines.

9. We call this kind of picture a  graph  – the points are called   vertices  and the lines or curves are called  edges . Our goal of finding “a walking tour that crosses each bridge once” is now matter of tracing out all the edges without lifting our pencil.

10. Euler’s solution to the original bridge problem Euler realized that trying to find a path by drawing the layout of the bridges and connecting them various ways would take a lot of time and would not necessarily result in a path that fulfilled the criteria . Instead he made the problem into a graph problem . In the corresponding graph each vertices are connected with odd number of edges(such vertices are called odd vertices ) .

11. If you start the path at one of the vertices, you can visit each vertices but one of the bridges is left out of the path as in the below example :

12. The path can be started at a different vertex or travel in a different order between the vertices, but there will always be at least one edge not left out. • This is because if an odd vertex is the starting point, you have to leave, then come back, then leave again for another vertex. • If that other vertex is also an odd vertex, then you have to leave after coming in and then come back again and there is no other edge to allow you to leave again for the other vertices. • Thus if there are odd vertices, the path must start and end at an odd vertex.

13. • So there can be at most 2 odd vertices. • This graph has four odd vertices so it is not possible to have a path where each edge is used exactly once.

14. “ THERE IS ABSOLUTELY NO PATH OVER THE KONIGSBERG BRIDGES ” Using this reason, Euler said that

15. This problem and solution or lack of solution to it became the start of the famous branch of Mathematics named “GRAPH THEORY”

16. THANK YOU