Discrete mathematics - Graph theory and algorithms

Teacher(s)

Blondel Vincent; Delvenne Jean-Charles;

Language

French

Prerequisites

This courses assumes that the elementary notions of discrete mathematics are acquired such as taught in LEPL1108.

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.

Learning outcomes

At the end of this learning unit, the student is able to :
1	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

Content

Structure and characterisation of graphs - basic concepts - degree, connected components, path, cycle, cut, minor, etc.  Exploration of graphs and tests of their properties - k-connectedness, Eulerian graphs, planar graphs, 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. Separation between "easy" and "hard" problems, NP-completeness.

Teaching methods

The course is organised in lessons and supervised exercise sessions.

Evaluation methods

The students are evaluated through assignments during the semester and through a written (or possibly oral depending on the circumstances) exam, based on the specific objectives described above. The semester assignments amount to 25% of the final grade (in January and in August). There is no opportunity to re-make assignments outside the semester. 
These assignments lead to a unique grade, given after the last assignment. Failure to respect the guidelines explained on Moodle, in particular regarding the use of online resources and/or collaboration between students, for any assignment may lead to a zero grade for the whole assignment grade.

Online resources

Moodle page of the course

Bibliography

Ouvrage de base (non obligatoire) / primary (non mandatory) reference :
Graph Theory with Applications, A. Bondy- U.S.R. Murty, Springer, téléchargement libre/free download
Aussi /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.

Teaching materials

• Notes de cours/lectures notes
• Transparents/slides

Faculty or entity

MAP