Note from June 29, 2020
Although we do not yet know how long the social distancing related to the Covid19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been  or will be  communicated to the students by the teachers, as soon as possible.
Although we do not yet know how long the social distancing related to the Covid19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been  or will be  communicated to the students by the teachers, as soon as possible.
5 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Blondel Vincent; Delvenne JeanCharles;
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, kcolorability 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.
Aims
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 :

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”.
Content
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  kconnected, 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
Teaching methods
The course is organized in lessons and supervised exercise sessions.
Evaluation methods
The students are evaluated individually through a written exam based on the specific objectives described above.
Online resources
Bibliography
Ouvrage de base :
Graph Theory with Applications, A. Bondy U.S.R. Murty, Springer, téléchargement libre
Aussi :
Graph Theory with Applications, A. Bondy U.S.R. Murty, Springer, téléchargement libre
Aussi :
 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.
Faculty or entity
MAP
Programmes / formations proposant cette unité d'enseignement (UE)
Title of the programme
Sigle
Credits
Prerequisites
Aims
Additionnal module in Mathematics
Minor in Engineering Sciences: Applied Mathematics (only available for reenrolment)
Specialization track in Applied Mathematics
Minor in Applied Mathematics
Master [120] in Computer Science and Engineering
Master [120] in Electrical Engineering
Master [120] in Computer Science
Master [120] in Statistic: General