Real life applications

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={V1, V2, V3, V4, V5}Let us first consider a candidate for dominating set as S1={V1, V2, V3}. 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={V1, V2}. 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 resources.

Similarly, dominating sets in graphs can be used in other applications such as:
School bus routing - As it is not practically possible to stop the bus for every student, instead we can use vertex of the graphs as bus stops and recognize minimum number of stops, which would be convenient for maximum number of people.


2. Vertex/Edge Coloring


We are taking an example here, where we want to schedule exams for Computer Science course with following course numbers: 1007, 3137, 3157, 3203, 3261, 4115, 4118, 4156
Consider that there are no students who have the following courses in common:
1007-3137
1007-3157, 3137-3157
1007-3203
1007-3261, 3137-3261, 3203-3261
1007-4115, 3137-4115, 3203-4115, 3261-4115
1007-4118, 3137-4118
1007-4156, 3137-4156, 3157-4156

Therefore, we have to find the minimum number of slots required to conduct exams for all the courses and all the students.

As there are 8 courses, the maximum slots that could be required would 8, but the challenge is to find the minimum number of slots.

Such complex problems, can be easily solved using vertex/edge coloring in graphs.



In a graph, let us represent the courses with the vertices and edges between the vertices where students are mutually excluded. From this graph we can see that courses 3157, 3203, 4118 cannot be put under same color. Similarly courses 3157, 3261, 4118 also cannot be put under same color. Therefore, we would need a minimum of 3 colors. From this we can conclude that we would need minimum of 3 exam slots.



We can observe that vertices with similar color are not adjacent to each other.


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