Aims
Demonstrate the value of graphs as a modelling tool. Develop the basics of graph theory, the characterisation and enumeration of different classes of graphs, the existence and search for optimal subgraphs, the complexity of calculating certain graph parameters.
Main themes
Introduction to the language and theory of graphs : questions of characterization, isomorphism, existence and enumeration. Properties of directed and undirected graphs such as connectivity, planarity, k-colorability and the property of being Eulerian, perfect, etc.
Modelling of practical problems : data structures and algorithms for the exploration of graphs.
Basic graph algorithms and an analysis of their complexity.
Content and teaching methods
Structure and characterization of graphs - basic concepts - degree, connected components, path, cycle, cut, minor, etc.
Classes of graphs and their recognition - perfect, series parallel, planar graphs, acyclic digraphs, etc.
Exploration of graphs and tests of their properties - k-connected, eulerian, etc.
Flows - theorems of Menger and Hall, maximum flow and minimum cost flow algorithms and their complexity.
Problems :finding optimal matchings and stable sets, the travelling salesman problem, cut, graph partitioning and graph colouring problems
Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)
Algorithmic Graph Theory, Alan Gibbons, Cambridge University Press 1985
Introduction to Graph Theory, Douglas West, Prentice Hall 1996.
Combinatorial Optimization, W.R. Cook et al., Wiley 1998.
Network Flows, Ahuja et al., Prentice Hall 1993.
Other credits in programs
ECGE3DS/SC
|
Diplôme d'études spécialisées en économie et gestion (Master in business administration) (Supply Chain Management)
|
(5 credits)
|
Mandatory
|
ELEC23
|
Troisième année du programme conduisant au grade d'ingénieur civil électricien
|
(5 credits)
| |
FSA12BA
|
Deuxième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil
|
(5 credits)
| |
INFO22
|
Deuxième année du programme conduisant au grade d'ingénieur civil informaticien
|
(5 credits)
| |
INFO23
|
Troisième année du programme conduisant au grade d'ingénieur civil informaticien
|
(5 credits)
| |
MAP21
|
Première année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(5 credits)
|
Mandatory
|
MAP22
|
Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(5 credits)
| |
MAP23
|
Troisième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(5 credits)
| |
MECA22
|
Deuxième année du programme conduisant au grade d'ingénieur civil mécanicien
|
(5 credits)
| |
|