2017-2018 / MATH0499-1

Graph theory

Duration

25h Th, 20h Pr

Number of credits

 Bachelor in computer science4 crédits 
 Master in data science (120 ECTS)4 crédits 
 Master in computer science (120 ECTS)4 crédits 
 Master in computer science (60 ECTS)4 crédits 
 Bachelor in mathematics4 crédits 

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