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

  • Why are we here? Landscape-level management needs for

    Why are we here? Landscape-level management needs for

    And therefore we care about... Diseases. Animal pests . Aquatic weeds . Rangeland weeds. Mussels . Forest pests . Why do we care about invasive plants? Not only do they degrade wildlife habitat, they also degrade ecosystem services we all...
  • ESSENTIAL ENGLISH ETAQ MASTERCLASS UNIT 3 MAY 2018

    ESSENTIAL ENGLISH ETAQ MASTERCLASS UNIT 3 MAY 2018

    Will have an excerpt in the exam. POLITICAL . CARTOON. Simple. Exposed to similar as prep. UNSEEN. UNIT 3 - CIA. Susan - how BSSC has implemented. Model CIA . SEEN. Explain how the audience is positioned to accept the...
  • Acute Kidney Injury Adding Insult to Injury Marlies Ostermann ...

    Acute Kidney Injury Adding Insult to Injury Marlies Ostermann ...

    Acute Kidney Injury Adding Insult to Injury Marlies Ostermann Consultant in Nephrology & Critical Care Guy's & St Thomas' Hospital, London Acute Kidney Injury Adding Insult to Injury Marlies Ostermann Consultant in Nephrology & Critical Care Guy's & St Thomas'...
  • 슬라이드 1 - mayrufo.weebly.com

    슬라이드 1 - mayrufo.weebly.com

    NEXT WEEK: Unit 2 Leisure. Suggested schedule for ONLINE Activities. Activities 1 and 2 -Friday. Activities 3, 4, 5 -Saturday Monday. Activity 6 and 7 -Sunday Tuesday
  • Designing forConstruction Site Safety- 2 to 4 hour

    Designing forConstruction Site Safety- 2 to 4 hour

    "Washington Group International Designs and Builds a Mixed-Waste Treatment Facility." OSHA. February 2007. This case study describes how the Washington Group International, Inc. incorporated its design for safety process into the construction of the U.S. Department of Energy's Advanced Mixed...
  • Regulatory Affairs Nick Littlebury nlittlebury@diamondpharmaservices.com Wednesday 10th October

    Regulatory Affairs Nick Littlebury [email protected] Wednesday 10th October

    Diamond BioPharm Limited, UK. Regulatory affairs is an interesting, challenging and rewarding career. The salary, benefits and career prospects are very good once you have got your foot in the door. Research the career thoroughly and get applying!
  • Quasimodo:

    Quasimodo:

    Syllables: Consonants. Typically syllables don't end with a consonant (though there are exceptions to this - like when the word ends with a consonant) Basic rule for figuring out if 2 consonants should work together or if they should be...
  • Apes Exam Review - Queenbegumscience

    Apes Exam Review - Queenbegumscience

    The AP Environmental Science Exam is 3 hours long and has two parts — multiple choice questions and free response questions. ... APES EXAM POWERPOINT YOUTUBE REVIEW . PART 1 OF 6. PART 2 OF 6. PART 3 OF 6....