The main aim of the course is to teach the students how to apply graph theoretical concepts to prove structural properties of graphs related to the topics described in the content of the course. More specifically, after following the course, the student can:
- explain and apply basic concepts of graph theory;
- explain and apply known properties of trees;
- explain and apply the concepts of vertex and edge connectivity;
- explain and apply the notions of Euler trail, Euler circuit and Hamilton cycle;
- explain and apply theorems concerning matchings in bipartite and non-bipartite graphs;
- explain and apply concepts and theorems about edge and vertex colouring;
- explain and apply theorems about planar graphs;
- prove new structural graph theoretical statements involving the above topics.
|
|
This course provides the students with a general introduction and understanding of central topics in graph theory. Apart from a general introduction to the basic concepts and definitions in Lecture 1, in each of the subsequent seven lectures, one graph theoretical topic is central and treated in more detail. This involves new definitions that are relevant for that particular topic, as well as associated structural results and their proofs. Lecture 2 deals with trees, a special class of graphs that are relevant for many applications. Trees are the basic structures needed to guarantee connectivity, which is the central topic of Lecture 3. In Lecture 4, the focus is on matchings, a concept used to model optimisation problems in which objects have to be paired off. This is generalised in Lecture 5 to edge colourings, which are relevant in scheduling problems. The analogous counterpart of vertex colourings is treated in Lecture 6 and in part of Lecture 7. The remaining part of Lecture 7 and the final lecture focus on the special class of planar graphs.
The lecture slides are supported by a downloadable book that is also available as a reader from the UnionShop.
|
 |
|