# 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
Q1
Teacher(s)
Blondel Vincent; Delvenne Jean-Charles;
Language
French
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.
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 : 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. 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
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
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
Sigle
Credits
Prerequisites
Aims
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