This courses assumes that the elementary notions of discrete mathematics are acquired and requires a sufficient mathematical maturity, equivalent to the level of a student having achieved the first year of engineering.
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.
AA1 : 1,2,3
More precisely, by the end of the course the student will be able to :
- model various problems in the language of graph theory
- identify if a graph-theoretic problem has a known efficent algorithmic solution or not
- propose and apply an algorithm to solve sucha a problem, at least for some classes of graphs
- prove in a clear and rigorous fashion elementary properties related to the concepts covered in the course
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
The students are evaluated individually through a written exam based on the specific objectives described above.
The course is organized in lessons and supervised exercise sessions.
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
Main reference:
Graph Theory with Applications, A. Bondy- U.S.R. Murty, Springer, téléchargement libre
Also:
- 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.
