 | | |
| MATH0499-1 | 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 |
|
Course 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
- kernel of a graph, application to combinatorial graph theory
- max flow/min cut in a network
|
|
Learning outcomes of the course :
|
| 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 deeply understood theoretical results for which he/she will be able to give a proof. He/she will be able to arrange several results and methods from the course to solve an exercise. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| Prerequisites are kept to a minimum (matrix computations, 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. Implementation of algorithms could also be considered during those sessions. |
|
Mode of delivery (face-to-face ; distance-learning) :
|
| Theoretical lectures using "blackboard and chalk" 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 :
|
| The examination consists of two parts: a written one and an oral one. The written part is devoted to the resolution of problems and exercises. The oral part is devoted to the theory (mainly proofs of theorems and presenting algorithms with a discussion) but also includes direct applications of the theory. |
|
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 |
|
|
