Study Programmes 2017-2018
MATH0499-1  
Graph theory
Duration :
25h Th, 20h Pr
Number of credits :
Bachelor in computer science4
Master in data science (120 ECTS)4
Master in computer science (120 ECTS)4
Master in computer science (60 ECTS)4
Bachelor in mathematics4
Lecturer :
Michel Rigo
Language(s) of instruction :
French language
Organisation and examination :
Teaching in the first semester, review in January
Units courses prerequisite and corequisite :
Prerequisite or corequisite units are presented within each program
Learning unit contents :
In this course, we consider classical notions arising in graph theory :


  • basic notions : graphs, multi-graphs, oriented graphs, paths and circuits
  • connected graphs
  • acyclic graphs, topological sort
  • subgraph, trees, covering trees
  • finding a path of minimal weight, Dijkstra's algorithm
  • Eulerian paths and graphs
  • Hamiltonian paths and graphs
  • Algebraic graph theory, counting paths in graphs, application to Google's page rank algorithm
  • bipartite graphs
  • planar graphs and Euler's formula
  • colouring problems, Ramsey numbers
  • max flow/min cut in a network
Learning outcomes of the learning unit :
At the end of this course, the student should have mastered fundamental notions arising in graph theory? He/she will be able to model a problem in terms of graph and apply the corresponding algorithms. The student will be able to give arguments about his/her assertions. He/she will have at his/her disposal a set of well understood theoretical results. He/she will be able to arrange several results and methods from the course to solve an exercise. 
Prerequisite knowledge and skills :
Prerequisites are kept to a minimum (matrix computations, computing determinants and characteristic polynomial, notion of eigenvalue/eigenvector). Concepts from complexity theory is valuable. No prerequisites about the mathematical software Mathematica is assumed.
Planned learning activities and teaching methods :
The course is focused on theoretical aspects. Exercise sessions are mainly dedicated to solve exercises corresponding to the theory considered during the lecture sessions. These sessions are also useful to obtain extra informations or enlightenments on the concepts presented during the lecture sessions.
Mode of delivery (face-to-face ; distance-learning) :
Theoretical lectures using "blackboard and chalk" + video material, interacting with students. During exercises sessions, students are facing exercises that must be solved.
Recommended or required readings :
Lecture notes are available (in french) and can be downloaded from http://www.discmath.ulg.ac.be/
Assessment methods and criteria :
For evaluation, two options are available. Each student must give the chosen option by the end of October.
1. First option (implementation project, exercises, reduced theoretical part):
A written exam is organized. During this examination, the student must be able to state and use  results and definitions from the course. The examination will also include several exercises related to the material covered during the course and the exercise sessions.
An implementation project is also part of the final grade. This project requires to providing a C code, a short written report to help understanding the code and an oral defense (individual questions). Details will be provided during the year. Unless explicitly stated, the different groups can neither collaborate nor be inspired by the code of other groups.
The final grade is based on the two scores: written examination and project.
2. Second option (no implementation project, exercises and theoretical range):
A written exam is organized. It focuses on the resolution of exercises related to the material covered during the course and the exercise sessions.
An oral examination is also organized. It consists of the presentation of algorithms, statements and proofs of results  (discussions and direct applications). Students should be able to expose proofs of results given during the course.
The final grade is based on the two scores: written and oral exams.
Work placement(s) :
Organizational remarks :
Some useful informations are given on http://www.discmath.ulg.ac.be/ In particular, one has access to the log of the year and also the ones of previous years.
Contacts :
M. Rigo Institut de Mathématique (B37) - Grande Traverse 12 -  Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 -  E-mail : M.Rigo@ulg.ac.be
Items online :
Notes de cours
ensemble des notes