Graph Theory is the branch of mathematics studying abstract networks, and is useful in any situation where we wish to analyse connections between objects. Such scenarios range from the theoretical, such as in the famous Bridges of Königsberg problem, to vital practical applications such as the kidney donor problem. Graph theory is noted for its accessibility, with concepts and questions that are easy to understand but which frequently hide deep and beautiful ideas below the surface; many problems which are simple to state remain open to this day.
Algorithms are precise sequences of instructions for solving mathematical or computational problems, such as computer programmes. At a theoretical level, it is important to understand how to optimise the performance of algorithms, and also their limitations: which problems cannot be solved efficiently by algorithm or indeed cannot be solved at all. Graph theory provides an excellent environment for the mathematical study of algorithms as the objects involved are simply but give rise to complex questions for algorithmic analysis.
This module gives an introduction to fundamental results and concepts in graph theory, such as Hall's matching theorem, and also to the basic ideas of algorithms and their analysis. These two concepts are then fruitfully combined in a range of ways: the theoretical ideas of graph theory illuminate key algorithmic ideas, whilst algorithmic analysis can also be used to solve problems in graph theory.
Learning Outcomes
By the end of the module students should be able to:
Be familiar with basic graph concepts such as matchings, colourings and trees, and related parameters such as the matching number and chromatic number.
Understand and be able to apply fundamental results about graphs.
Be familiar with the concepts of an algorithm and be able to analyse basic algorithms for problems in graph theory.
Be familiar with basic graph concepts such as matchings, colourings and trees, and related parameters such as the matching number and chromatic number.
Assessment
Assessment Methods & Exceptions
Assessment:
2hr examination (80%) In-course assessment (20%) (including a variety of assessment possibly including problem sheets, class tests, online quizzes and group projects)
