Close Help Print
 Course module: 191520751
 191520751Graph Theory
 Course info
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)
 Examiner prof.dr.ir. H.J. Broersma Contactperson for the course prof.dr.ir. H.J. Broersma Examiner dr.ir. P. van 't Hof
Starting block
 2A
RemarksThis course is also an elective of B-AM module 11.
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 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.
 Content
 body { font-size: 9pt; font-family: Arial } table { font-size: 9pt; font-family: Arial } 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.
 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
 Written exam
 Close Help Print