Close Help Print
 Course module: 191520751
 191520751Graph Theory
 Course info Schedule
Course module191520751
Credits (ECTS)5
Course typeCourse
Language of instructionEnglish
Contact personprof.dr.ir. H.J. Broersma
E-mailh.j.broersma@utwente.nl
Lecturer(s)
 Contactperson for the course prof.dr.ir. H.J. Broersma Examiner prof.dr.ir. H.J. Broersma Lecturer dr.ir. P. van 't Hof
Starting block
 2A
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
 Aims
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } The main aim of the course is to provide the students with a general introduction and understanding of the basic concepts and central topics in graph theory. The specific learning goals of the course are that at the end of the course, the students: can recall the basic concepts and structural results that are treated in the course; can explain and apply the theorems and the proofs that have been discussed; understand the solutions to the exercises that are listed for the tutorials; are able to apply their knowledge to solve new exercises; are able to develop new proofs for variants of the results that have been explained; are aware of the relevance of the treated topics for applications; can apply their knowledge to model new problems as graph problems.
 Content
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } This course is meant to provide the students with a thorough introduction to graph theory and its applications. 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 will be central and treated in more detail. This will involve new definitions that are relevant for that particular topic, as well as associated structural results and their proofs. Lecture 2 will deal 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, modelling optimisation problems in which objects have to be paired off. This is generalised in Lecture 5 to edge colourings that 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 will focus on the special class of planar graphs, that can be drawn in the plane avoiding crossings. The lecture slides will be supported by a downloadable book that will also be made available as a reader from the UnionShop.
 Module
 Module 11
 Participating study
 Master Computer Science
 Participating study
 Master Applied Mathematics
 Participating study
 Bachelor Applied Mathematics
Required materials
Literature
 To be announced by the lecturer
Recommended materials
-
Instructional modes
 Lecture Tutorial
Tests
 Exam
 Close Help Print