Sluiten Help Print
 Cursus: 191520751
 191520751Graph Theory
 Cursus informatie
Cursus191520751
Studiepunten (ECTS)5
CursustypeCursus
VoertaalEngels
Contactpersoonprof.dr.ir. H.J. Broersma
E-mailh.j.broersma@utwente.nl
Docenten
 Contactpersoon van de cursus prof.dr.ir. H.J. Broersma Examinator prof.dr.ir. H.J. Broersma Examinator dr.ir. P. van 't Hof
Collegejaar2022
Aanvangsblok
 2A
OpmerkingThis course is also an elective of B-AM module 11.
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
 Cursusdoelen
 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.
 Inhoud
 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.
 Participating study
 Master Computer Science
 Participating study
 Master Applied Mathematics
 Participating study
 Bachelor Applied Mathematics
 Module
 Module 11
Verplicht materiaal
Literature
 To be announced by the lecturer
Aanbevolen materiaal
-
Werkvormen
 Hoorcollege Werkcollege
Toetsen
 Written exam
 Sluiten Help Print