Programme And Module Handbook
 
Course Details in


If you find any data displayed on this website that should be amended, please contact the Curriculum Management Team.

Module Title Graph Theory
SchoolMathematics
Department Mathematics
Module Code 06 19592
Module Lead Dr D Hermans
Level Honours Level
Credits 20
Semester Full Term
Pre-requisites Foundation and Abstraction - (06 22512)
Co-requisites
Restrictions Optional for: All MSci programmes in Mathematics, BSc Mathematical Sciences, BSc Mathematical Sciences with Study in Continental Europe, All programmes including a Major in Mathematics, All JH programmes
Contact Hours Lecture-46 hours
Seminar-0 hours
Tutorial-10 hours
Project supervision-0 hours
Demonstration-0 hours
Practical Classes and workshops-0 hours
Supervised time in studio/workshop-0 hours
Fieldwork-0 hours
External Visits-0 hours
Work based learning-0 hours
Guided independent study-0 hours
Placement-0 hours
Year Abroad-0 hours
Exclusions
Description The module will give an introduction to fundamental results and concepts in graph theory. This is an area of Pure Mathematics which underpins much of the digital economy. Topics are likely to include Hamilton cycles, graph matchings, connectivity, graph colourings, planar graphs and extremal graph problems. For example, a fundamental result in Graph Theory is Hall’s marriage theorem, which characterizes all bipartite graphs that can be split into compatible pairs. Another famous result is the four colour theorem, which states that every planar map can be coloured with at most four colours such that adjacent regions have different colours (this can be translated into a graph colouring problem and has applications to scheduling).
Learning Outcomes By the end of the module the student should be able to:
  • Be familiar with basic graph parameters and their relationships, such as connectivity, vertex covers and chromatic number.
  • Understand and be able to apply fundamental results on graphs (such as Hall’s theorem, Menger’s theorem, Dirac’s theorem and Turan’s theorem).
  • Apply the basic techniques introduced in the lectures.
Assessment 19592-04 : Raw Module Mark : Coursework (0%)
19592-05 : Final Module Mark : Coursework (100%)
Assessment Methods & Exceptions Assessments: 19592-01: Exam : Exam (CT) - Written Unseen (90%)
19592-02 : Continuous Assessment : Coursework or class tests (10%)
Other
Reading List Bondy, J A & Murty, U S R. 1976. Graph Theory with Applications. North-Holland.
West, D. 2001. Introduction to Graph Theory. Prentice Hall.
Diestel, R. 2000. Graph Theory. 2nd ed. Springer Verlag.
Electronic version: http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html