How it all started? - Seven Bridges of Königsberg

So let's look at the introduction of graph theory in real world. So it started from Russia. There is a Russian city called Königsberg. It has seven bridges which are constructed to connect two Islands.

The concern about these bridges was that the people would have to walk through the city by crossing all the seven bridges and you can only be walking one bridge at a time. So let us look at the picture given below

So to solve this problem first of all we cannot skip any bridge and we can only cross a bridge once.

A lot of people tried but this puzzle seemed impossible to them.

So a Russian mathematician Leonard Euler tried to solve this and came up with a reason that why this is such a hectic job. 

In the image as we can see there are four different lands and two Islands (b and d). Two parts of the mainland (a and c) and total seven bridges.

Each land is connected with an odd number of bridges as shown in the figure.

We can break down this image and can form a number of conclusions. So firstly each land is connected with an odd number of bridges. If we wish to cross each bridge only once then you can enter and leave a land only if it is connected to an even number of bridges. 

In simple words, we can say that if there are even number of bridges it is possible to crack this puzzle while it's impossible to crack this with odd number of bridges.

So let's add another bridge in the image and see if we can solve this puzzle

Now we have 2 lands which are connected with even number of bridges and 2 lands which are connected with odd number of bridges.

Now let's draw a new route after adding the new bridge.

But adding a new bridge solved the problem completely!

So you might be wondering if the number of bridges are significant to solve this problem?

Do the bridges have to be even every time?

Well the answer is no.

The mathematician explained that with the number of bridges, the number of pieces of land with an odd number of connected bridges are significant as well. He converted this problem from land and bridges to graphs, where he represented the land as vertices and the bridges as edges of the graph as shown below.



Comments

Post a Comment

Popular posts from this blog

Introduction

“There is a magic in graphs. The profile of a curve reveals in a flash a whole situation — the life history of an era of prosperity. The curve informs the mind, awakens the imagination, convinces.” – Henry D. Hubbard Visualizations is a powerful way to simplify and know about the underlying patterns in data. The first thing you should be doing, whenever working on a new dataset is to explore it through visualization. This approach has done wonders for anyone who does so. Sadly, we don’t see many people using this visualization technique as much. That is why we thought to share this “secret ingredient” with the world! Use of graphs is one such visualization technique. It becomes very useful for businesses to make better data-driven decisions. But to understand the concepts of graphs in detail, we will first have to first dive in deep into it to understand it’s base that is Graph Theory. Graph theory represents one of the most important, interesting and innovative areas in computer science...
Read more

Real life applications

Image
1. Dominating sets in graph Let's take an example, where we want to open up a departmental store. So, our goal should be opening minimum number of stores that would capture maximum area. We will take help of graphs here and convert this into a question of dominating sets in graph. Here our set of vertex is V={ V 1 ,   V 2 , V 3 , V 4 , V 5 } Let us first consider a candidate for dominating set as S1={ V 1 ,   V 2 , V 3 }. We can observe that every element of set V is adjacent with at least one element of S1. So, is S1 our final dominating set? No, because it is not unique. Let us consider another candidate for dominating set S2={ V 1 ,   V 2 }. If we compare set V and S2, then it is observed that elements of set V are also adjacent with elements of set S2. So we will consider set S2 as our option for dominating set as it has the minimum number of elements possible in a dominating set. Remember, we had to find a solution which would give maximum output with minimum resourc...
Read more