Posts

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...
1 comment
Read more

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

Image
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....
1 comment
Read more

Fundamentals of Graph

Image
Let us consider a graph G=(V,E) in which V is a pair of vertices (or nodes) and E stands for set of edges. Broadly there are two types of graphs, directed graph and undirected graph.               Visualizations is considered one of the most efficient method to simplify and interpret the underlying patterns in data. Firstly, while working on any new dataset, one should  explore it through visualization. This approach gives fruitful result for anyone who does so. Sadly, we don’t see this method common among many people. Here in the example we can see that  V 1 ,   V 2 , V 3 , V 4 , V 5  are the vertices of the graph and E 1 ,   E 2 , E 3 , E 4 , E 5 , E 6   are the edges of the graph. Let us take an example of an edge E k =(V i, V j ) is incident with the vertices V i  and V j .   The vertices V i  and V j  are called as adjacent vertices. The degree d(v) of a vertex V tells us that it is number of incid...
1 comment
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...
1 comment
Read more

Conclusion

These are just some of the many applications of Graph Theory. We can apply it to almost any kind of problem and get solutions and visualizations. Some of the application of Graph Theory which we can think of are: Representing networks of communication. For example, link structure of a website can be represented using directed graphs. Determining the social behavior of a person using their social connection graph These are some of the applications.   There is still so much to tell about graphs. Take this blog as another tip of the iceberg. If you have read this far, you definitely deserve a cookie. Don’t forget to clap and share. Thank you!
1 comment
Read more