It is strange how Mathematics can pursue one even when out on a leisurely stroll ! This is exactly what happened to the people of a laid back city called Konigsberg a couple of centuries back.
Konigsberg is a city formerly in Germany but now in Russia and is called Kaliningrad. River Pregel flows through the city and divides it into two islands and two banks There were seven bridges connecting the different part of the city with each other. The people of Konigsberg always wondered whether it was possible to start from one point and cross all the bridges only once and come back to the same point.
|
The Konigsberg Bridges |
What were they thinking?? Couldn't they just enjoy the stroll around the river peacefully and not make life so complicated? Apparently not and thanks to them a new field in Mathematics was subsequently developed called Topology.
It so happened that a Swiss mathematician called Leonhard Euler was the first to solve this problem. In the process, he introduced the branch of Mathematics called Topology. He used an area in Topology called Networks. A network is a group of points, which are called vertices, and a collection of lines, called edges, connecting these points.
|
The Konigsberg Network |
He must have got both tired and fed up of walking the bridges to solve the problem that he decided to draw the map of the bridges on a paper and solve the problem sitting at home! So this is what it looked like. A,B,C And D are the land mass (vertex) and a,b,c,d,e,f and g are the bridges (edges).
He made the remarkable discovery ( The Graph Theory) that whether a network is traversable depends on the number of odd vertices. In the Königsberg network, there are an odd number of edges (a,b,f) at point A, so A is called an odd vertex. If the number of edges meeting at a point is even, the point is called an even vertex.
Traversable Networks
1. A network with exactly two odd vertices is traversable.
2. A network with no odd vertices is traversable.
3. A network with more than two odd vertices is not traversable.
Since the Königsberg network has four odd vertices ( all vertices A,B,C AND D have odd edges meeting them) it is not traversable. As this Graph, is not Eularian, therefore, it is not possible to take a walk over the bridges of Königsberg and cross each bridge only once.
A Network has a Euler Path if every edge in the network is traversed only once without lifting the pencil from the paper.
Now do you remember those tricks that our friends challenged us in childhood?? If we could draw a certain figure without lifting our pencil from the paper. I particularly remember this one but there were more impossible ones as well . If only we knew then that it was pure Mathematics playing up!
*If you can remember any more figures do post them here. There will be more exciting posts on the Euler Paths .