Study programme 20202021  Français  
Graphs and Combinatorial Optimisation  
Programme component of Master's in Mathematics à la Faculty of Science 
Students are asked to consult the ECTS course descriptions for each learning activity (AA) to know what special Covid19 assessment methods are possibly planned for the end of Q3 

Code  Type  Head of UE  Department’s contact details  Teacher(s) 

USM1SCMATH019M  Optional UE  TUYTTENS Daniel  F151  Mathématique et Recherche opérationnelle 

Language of instruction  Language of assessment  HT(*)  HTPE(*)  HTPS(*)  HR(*)  HD(*)  Credits  Weighting  Term 

 Français  36  12  0  0  0  4  4.00  1st term 
AA Code  Teaching Activity (AA)  HT(*)  HTPE(*)  HTPS(*)  HR(*)  HD(*)  Term  Weighting 

IMARO011  Graph Theory and Combinatorial Optimization  36  12  0  0  0  Q1  100.00% 
Programme component 

Objectives of Programme's Learning Outcomes
Learning Outcomes of UE
Understand the fundamental notions and problems appearing in graph theory;study the corresponding algorithms;go deeply into algorithmic notions from the algorithm efficiency point of view;understand the fundamental problems and techniques of combinatorial optimization;illustrate some methods on some particular problems;show the utility of algorithms for solving practical problems in scheduling management, logistics,...
Content of UE
Basic notions of graph theory and data structure; study of classical graph theory problems : trees, shortest paths, connexity, flows;introduction to complexity theory : P and NP classes; study of classical combinatorial optimization problems : knapsack, set covering, travelling salesman; introduction to metaheuristics.
The teaching methods are likely to be adjusted according to the educational context
imposed by the health measures.
Prior Experience
Linear programming; duality; notion of algorithm.
Type of Assessment for UE in Q1
Q1 UE Assessment Comments
Report of project/challenge : 20%. Written examination covering both parts of the course: Graph theory : (theory and exercises) 40% Combinatorial optimization : (theory and exercises) 40%
The evaluation procedures are likely to be adjusted according to
the educational/assessment context imposed by health measures.
Type of Assessment for UE in Q3
Q3 UE Assessment Comments
Report of project/challenge : 20%. Written examination covering both parts of the course: Graph theory : (theory and exercises) 40% Combinatorial optimization : (theory and exercises) 40%
The evaluation procedures are likely to be adjusted according to
the educational/assessment context imposed by health measures.
Type of Resit Assessment for UE in Q1 (BAB1)
Q1 UE Resit Assessment Comments (BAB1)
Not applicable
Type of Teaching Activity/Activities
AA  Type of Teaching Activity/Activities 

IMARO011 

Mode of delivery
AA  Mode of delivery 

IMARO011 

Required Reading
AA  

IMARO011 
Required Learning Resources/Tools
AA  Required Learning Resources/Tools 

IMARO011  Not applicable 
Recommended Reading
AA  

IMARO011 
Recommended Learning Resources/Tools
AA  Recommended Learning Resources/Tools 

IMARO011  Not applicable 
Other Recommended Reading
AA  Other Recommended Reading 

IMARO011  P. Lacomme, C. Prins & M. Sevaux Algorithmes de graphes, Editions Eyrolles, 2003. J. Dréo, A. Pétrowski, P. Siarry & E. taillard Métaheuristiques pour l'optimisation difficile, Editions Eyrolles, 2003. 
Grade Deferrals of AAs from one year to the next
AA  Grade Deferrals of AAs from one year to the next 

IMARO011  Authorized 