Discrete mathematics - Graph theory and algorithms

linma1691  2020-2021  Louvain-la-Neuve

Discrete mathematics - Graph theory and algorithms
Due to the COVID-19 crisis, the information below is subject to change, in particular that concerning the teaching mode (presential, distance or in a comodal or hybrid format).
5 credits
30.0 h + 22.5 h
Blondel Vincent; Delvenne Jean-Charles;
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.

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
Structure and characterisation 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
Teaching methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

The course is organised in lessons and supervised exercise sessions.
Evaluation methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

The students are evaluated through small projects during the semester and through a written (or possibly oral depending on the circumstances) exam, based on the specific objectives described above.
Online resources
Moodle page of the course
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
Force majeure
Evaluation methods
The exam is written, on site. An exam of adapted form will be proposed to the students with a valid quarantine certificate or a 'formulaire retour' from the Foreign Office, if the coordinating teacher (Jean-Charles Delvenne) is warned asap and in any case before the main exam. This alternative exam will cover the same topics as the main exam, and will be organised in a form compatible with the situation of the student.

Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Minor in Applied Mathematics

Master [120] in Computer Science and Engineering

Master [120] in Computer Science

Master [120] in Electrical Engineering

Additionnal module in Mathematics

Minor in Engineering Sciences: Applied Mathematics (only available for reenrolment)

Specialization track in Applied Mathematics