10-11-2012, 11:54 AM
Introduction to Graph-Theory and Applications
Introduction to Graph.pptx (Size: 1.02 MB / Downloads: 128)
Motivation
What is the common link between the following problems: traffic network design and cancer research?
Arranging marriages and scheduling flights?
Finding cure for mental illness, computer chip design, architectural floor planning, fighting terror online?
Fighting epidemics, e-commerce, designing voting schemes, job assignment, designing electrical networks, deciding on facility location, etc. etc. etc.
Graphs as models
Personnel assignment problems. (assigning people to jobs, arranging weddings, finding appropriate roommates, etc.)
Social networks.
VLSI chip design. (Planar graphs, visibility,…)
Geometric polyhedra (Rigidity of structures,)
Chemistry
Biology
Timetabling problems
m teachers, n classes.
Teacher i is required to teach class j for Pij periods.
In a given period a teacher can be in at most 1 class, and a class can have at most 1 teacher.
Design a timetable with minimum no. of periods.
Tractable!
Timetabling problems –complications
A limited number of classroom are available.
If there are l lessons scheduled in a p-period timetable, then how many rooms are needed?
At least {l/p} rooms are needed.
It is possible to arrange l lessons in p periods where at most {l/p} rooms are occupied in any one period.
More complications: teachers are not available for every period, they need their tea breaks, etc. etc.
Traffic network design problems
Cities have a growth of vehicle fleets
Good mobility and accessibility to goods, labour, and markets permit and encourage urban concentration.
Good transportation is necessary for jobs, business, basic utilities.
Transportation usually occupies 20-40% of city’s physical space
Problems: Change traffic patterns to allow a more efficient flow of transportation.
Design a traffic network which is fault-tolerant.
Facility location: k-median problem
Given a weighted graph, specified vertices called clients. Need to place facilities in k vertices in the graph which will serve the clients best possible. .
Minimize the distance of a client to each closest facility.
Facilities also have costs.
DNA sequencing
The building blocks of a DNA molecule are nucleotide bases—Adenine, Guanine, Cytosine, and Thymine (AGCT.) arranged in a sequence.
Length of sequence is order of 3x10*9
A special technology allows us to “see” fragments of length 500-1200 nucleotides.
How do we piece them together to find out the whole sequence of the DNA?
Difference in DNA between 2 people is less than 0.1%.