Graph Coloring and Allotting Gates for Flights

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!!

Recently Viewed Presentations

  • The Effects of Nutrient Pollution on the Neuse River Estuary

    The Effects of Nutrient Pollution on the Neuse River Estuary

    The Effects of Nutrient Pollution on the Neuse River Estuary ... as well Phytoplankton are base of the food chain Organisms selectively feed Pfiesteria and other toxic blooms Alter community structure Sources of nutrient pollution Anthropogenic Urban: wastewater treatment plants...
  • The Past Simple Tense - Energia Barreiros

    The Past Simple Tense - Energia Barreiros

    Ruti studied Japanese for five years. They sat at the beach all day. They did not stay at the party the entire time. We talked on the phone for thirty minutes. 4.The Simple Past can also be used to describe...
  • Changing subnational fertility trends in England and Wales

    Changing subnational fertility trends in England and Wales

    TFR pattern for E&W evident for each region - All regions experience a record low TFR in either 2001 or 2002 Distribution of local authority TFRs 1986, 2001, 2006 9 Pendle 12 Rochdale 14 Hackney and City of London 14...
  • Looking Glass Self - Learning with Skalberson

    Looking Glass Self - Learning with Skalberson

    Looking-glass self: a self-concept based on our idea of others' judgments of us. (1) We Imagine How We Appear to Others. I'm Very Cool (2) We Interpret Others' Reactions
  • Bacteria - KSU Faculty

    Bacteria - KSU Faculty

    Endospores. Endospores may remain dormant for 100 years or even longer. Immersion in boiling water for hours may not kill them. Endospores that survive these treatments can germinate or exit the dormant stage, to become a typical multiplying cell, called...
  • SUSE BU Presentation Template 2014

    SUSE BU Presentation Template 2014

    "We believe SUSE has the best Linux distribution with the best support. The platform goes beyond "five 9s," and the new environment results in considerable time savings for planned downtime." Eric Breuer, Manager Large Systems Baldor Read Full Case Study...
  • DAREA DE SEAMA A ACADEMIEI ROMANE PENTRU ANUL

    DAREA DE SEAMA A ACADEMIEI ROMANE PENTRU ANUL

    C. Agenda Digitala 2014 - 2020. Strategia Agendei Digitale 2014 - 2020 este elaborata de Ministerul pentru Societatea Informationala si are in vedere dezvoltarea sectorului IT&C romanesc, dar si imbunatatirea productivitatii sectorului privat prin reducerea barierelor administrative in relatia cu...
  • Promises Made to the Fathers

    Promises Made to the Fathers

    The Covenant God Made with Enoch. Moses 7. Will not destroy the world by flood (of water) again (Moses 7:51) Will call upon the children of Noah (i.e., will call the posterity of Noah to repent and come unto Christ;...