 | |
| MATH0249-1 | Graph theory
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
|
|
| Holder(s) : | Michel Rigo |
|
| Language : | Langue française |
|
| Course contents : | Graph theory is a part of discrete mathematics. It can be used to give a formal definition of various structures and problems and it has numerous applications in operational research, computer science, combinatorics, group theory, formal languages theory, ...
We present basic notions of graph theory. We study graphs by insisting on their theoretical aspects as well as on the corresponding algorithmic issues. |
|
| Course objective : | After presenting the main classes of graphs (directed graphs, non-oriented ones, multi-graphs, weighted graphs), the lectures will be devoted to present various classical questions in graph theory :
- paths in graphs (Eulerian and Hamiltonian circuits and paths)
- connectedness
- planar graphs
- trees
- spanning trees
- flows in a graph
- graph decompositions
- algebraic graph theory
- colouring problem
- combinatorics on graphs
|
|
| Prerequisites : | Basic notions in linear algebra. Knowledge of an imperative programming language is not compulsory. |
|
| Organization : | Lectures are dedicated to theoretical aspects of graphs. Practical sessions are devoted to solve exercises and to enlighten the concepts and the algorithms presented during the lecture. Detailed schedule will be given at the beginning of the academic year. |
|
| Written notes : | Lecture notes are available (in french) and can be downloaded from http://www.discmath.ulg.ac.be/ (http:///) |
|
| Assessment : | The final examination is in two parts. An oral part devoted to the theory (mainly proofs of theorems) but also direct applications of the theory. The written part is dedicated to the resolution of exercises and problems. The expected knowledge needed for this examination will be officially announced during the year. |
|
| Contacts : | M. Rigo
Institute of Mathematics (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarks : | Remarks : Some useful informations are given on http://www.discmath.ulg.ac.be/
|
|
