Fundamentals of Graph

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 V1, V2, V3, V4, V5 are the vertices of the graph and E1, E2, E3, E4, E5, E6 are the edges of the graph.

Let us take an example of an edge Ek=(Vi,Vj) is incident with the vertices Vi and Vj. The vertices Vi and Vj are called as adjacent vertices. The degree d(v) of a vertex V tells us that it is number of incident edges on that particular vertex. In this particular blog, we will be focusing on two of the graph concepts. They are: 1. Dominating sets in graph and 2. Vertex/Edge coloring in graph

1. Dominating sets in graph

A set S С V(G) of vertices in a graph G is a dominating set if every vertex VєV(G) is an element of S or adjacent to an element of S.

2. Vertex/Edge coloring in a graph

Vertex coloring of a graph is assignment of colors to the vertices such that no two adjacent vertices receive the same color. Similar can be done for vertex coloring, where no adjacent edges should have the same color. We have to make sure that we are using minimum number of colors to get the optimum solution.


                                     


Comments

Post a Comment

Popular posts from this blog

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

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