Graph theory

Duration

25h Th, 20h Pr

Number of credits

Lecturer

Michel Rigo

Language(s) of instruction

French language

Organisation and examination

Teaching in the first semester, review in January

Schedule

Schedule online

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.

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, hybrid learning)

Blended learning


Additional information:

Theoretical lectures using "blackboard and chalk" + video material, interacting with students. During exercises sessions, students are facing exercises that must be solved. Part of the teaching hours may be given in the form of a video to be viewed at a distance and supplemented by question/answer sessions.

Recommended or required readings

Lecture notes are available (in french) and can be downloaded from http://www.discmath.ulg.ac.be/
See also

• M. Rigo, Advanced graph theory and combinatorics, ISTE-Wiley (2016).

Exam(s) in session

Any session

- In-person

written exam ( open-ended questions )

Written work / report


Additional information:

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 or Python 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. A serious deficiency in one of the two parts will penalise the final mark. 

2. Second option (no implementation project, exercises and theoretical range):

A written exam is organized. It has two parts. One focuses on the resolution of exercises related to the material covered during the course and the exercise sessions. The second part 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 scores on the two parts. A serious deficiency in one of the two parts will penalise the final mark. 

Work placement(s)

Organisational remarks and main changes to the course

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

Association of one or more MOOCs

Items online