Konigsberg Bridge: An Example of Graph Theory

We often experience of seeing islands on rivers; at the middle of a big river. The stream comes from one direction and gets divided by the island. Then flows into two streams and gets united again after the island. These are very common natural scenarios with many river flows on low land areas.  You may check for such nearby river areas of your reach. Let me get into the topic here; why the bridge is there.

History

Kaliningrad is a small town in Russia, which was known as Konigsberg in eighteenth century or earlier. The town was built by the flow of the river Pregel. A big island was at the middle of the river. It was divided into two streams due to the island, got united again and continued in two directions again. Habitats grew on both sides and on the island. There were many bridges built to connect people from both sides for life. Actually seven bridges were built. The island was called Kniphof. The seven Konigsberg bridges were used to connect three land parts by two sides of the river and Kniphof. On a holiday, a long walk could cover all these bridges one after another. The dwellers in the town were happy enough to walk through the bridges and feel the nature in those days. Gradually a maze and ultimately a challenge had been developed about crossing all of the bridges starting from one point and coming back to the same. Can a person start walking from a point and come back to the same by crossing all seven bridges only once? Nobody was successful though many tried years after years in early eighteenth century. Al last in 1736, the famous Swiss Mathematician Leonard Euler made an explanation for this puzzle by a mathematical theory.

Graph Theory

The Mathematics behind this problem of Konigsberg Bridges is Graph Theory. Mathematicians have worked and been working on this for solving many real life problems so far. Sometimes the problems are so complicated that computer programs are necessary to process calculations. Computer programs were not used in eighteenth century when Leonard Euler (1707-1783) first wrote a scholarly article on Graph Theory, which was not then a recognized branch in Mathematics.  A graph is actually a system of points with some specific connections. Graph is not same as chart sometimes people get confused with. Graph expresses relationships amongst points, such as, computer network at an office or road communication among cities of a state. Here each of the cities or points is called a vertex and each connecting road or line is called an edge. In a graph, every point may not have equal number of edges. A graph can be written as a set like {4, 3, 2, 2, 1}. Here there are five points in the graph, number of edges associated with each point are shown in the set in descending order. Sum of the numbers, that is, sum of the degrees, in such set is always even and double of the number of edges in a graph. A sequence of vertices along with their edges is called a path. A circuit can be made when a path starts from a point and ends at the same.  Eulerian Path of a graph crosses all the edges of a graph by reaching vertices one after another, but no edge is crossed more than once.  Eulerian Circuit is the Eulerian Path, which starts from and ends at a same vertex.

Solution

Graphs_Konigsburgh

Eulerian Circuit may exist for a graph if and only if each vertex is of even degrees. {4, 2, 2, 2, 2} is an example Eulerian graph, where you can start from a point and come back to the same by crossing all the edges only once.  Eulerian Path may exist for a graph when there are only two vertices with odd degrees. These are called semi-Eulerian graph. {4, 3, 2, 2, 1} is an example of semi-Eulerian graph, where you can start from an odd degree vertex, 3 or 1 in this case, and reach at the other by crossing all the edges only once.

Our Konigsberg Bridge problem is graph with four vertices as the four land parts. Each land part is connected to another through bridges. So the graph is represented as a sequence all odd numbered vertices as {5, 3, 3, 3}. This is neither an Eulerian nor a semi-Eulerian graph for which Eulerian Circuit or Eulerian Path exists. That means, it is not possible to start from a land part and come back to the same by crossing all the seven bridges only once.

3 Replies to “Konigsberg Bridge: An Example of Graph Theory”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s