# Graph Coloring and Allotting Gates for Flights A problem with train tracks and interval graphs PRESENTED BY MANVITHA NELLORE OBJECTIVES Real World Problem Proposed Solution Interval Graph Special Properties Interpreting graph solution to real life problem Problem Solution Graph coloring Summary

Real World Problem As there are very busy cities in this world they may face a problem with train tracks. In some cities we have very few tracks and many trains in which their will be a moving trains one after the other from both sides. So , their shouldnt be any colliding they must have some perception before itself. This may help in avoiding train trafficking and train accidents. Proposed Solution This can be solved by allotting tracks to trains by scheduling trains with time intervals without time conflicts with other train. Trains which come on same time should assign different track in one station, this avoid waiting time for other trains. A proper solution can be given for some tracks by taking set of trains as vertices and time conflict as edges. We allot train timings in different

tracks in stations by using graph theory. Interval Graph A graph G is an interval graph if we can represent the intervals on a number line such that two vertices are joined by an edge if and only if their corresponding intervals overlap. SPECIAL PROPERTIES Graph coloring: Given a graph, color all the vertices so that two adjacent vertices get different colors. Complete Graphs: Every vertices should have a edge between each other vertices. Chromatic number:

The chromatic number of a graph is the smallest number of colors needed to color the vertices, so that no two adjacent vertices share the same color the smallest value of possible to obtain a k-coloring. Umbrella - free ordering : An umbrella-free representation of a graph G is a concatenation of all its connected component. Interpreting graph solution to real life problem This problem can be solved by using graph coloring concept by coloring the vertices by using chromatic number concept to color vertices with minimum number of colors. Colors got by edges are the tracks for which we are allocating tracks for trains.

Problem Solution Lets consider seven trains and assign them with alphabets, they are A,B,C,D,E,F,G. Firstly we can allot some timings to the train in random time intervals. Train : Time duration A : 1-3 B : 6-8 C

: 2-5 D : 10-12 E : 2-7 F : 6-11

G : 4-9 Problem Solution Keep this time intervals in an interval graph where we may see time conflicts between the train timings. g f e d c

b a 0 1 2 3 4 5 6

7 8 9 10 11 12 We can see in Black line 4 trains come to same station at different tracks at same time. Graph Coloring Construct a graph by using interval graph and arrange the vertices and edges. By using Graph coloring we have colored following vertices and got different colors as follows.

b a d c e f g Graph Coloring By using chromatic number we have colored the vertices and got minimum K colors.

4 colors (Purple , Yellow, blue , Green) Colors which we got by edges are the tracks which we are Allocating for trains. Finally the allocation of tracks by using coloring graphs results to: Tracks: 1 2 3 4 Purple

Yellow Blue Green A,G,D C,F B E Suddenly if any new train would like to come into same station then we can

allot any track by considering(check the time intervals of trains in all tracks) that which is free at that time. SUMMARY Graph coloring is useful in modeling problems in real life. It is an important problem in graph theory. We can use this in many applications where we find time conflicts and can solve them by allocating time intervals. REFERENCE Interval Graph

https://en.wikipedia.org/wiki/Interval_graph Graph coloring http://en.wikipedia.org/wiki/Graph_coloring Graphcoloring.(ppt) http://csis.bitspilani.ac.in/faculty/goel/course_materi al/DISCRETE%20STRUCTURES/2011/Graph%20Colori ng.ppt http://ravi.cs.sonoma.edu/cs315fa08/Lectures/lec24dec11-f08.ppt http://www.cse.cuhk.edu.hk/~chi/csc2110/notes/ L09.ppt Queries ?

Thank you!!