Graphs and Combinatorics - MA595

Location Term Level Credits (ECTS) Current Convenor 2019-20
Canterbury Spring
View Timetable
6 15 (7.5)

Pre-requisites

For delivery to students completing Stage 1 before September 2016:
Pre-requisite: MA322 (Proofs and Numbers);
Co-requisite: None

For delivery to students completing Stage 1 after September 2016:
Pre-requisite: MAST4001 (Algebraic Methods) or MAST4005 (Linear Mathematics)
Co-requisite: None

Restrictions

None

2019-20

Overview

Combinatorics is a field in mathematics that studies discrete, usually finite, structures, such as graphs. It not only plays an important role in numerous parts of mathematics, but also has real world applications. In particular, it underpins a variety of computational processes used in digital technologies and the design of computing hardware.
Among other things, this module provides an introduction to graph theory. Graphs are discrete objects consisting of vertices that are connected by edges. We will discuss a variety of concepts and results in graph theory, and some fundamental graph algorithms. Topics may include, but are not restricted to: trees, shortest paths problems, walks on graphs, graph colourings and embeddings, flows and matchings, and matrices and graphs.

Details

This module appears in:


Contact hours

42-48 lectures and example classes

Method of assessment

80% Examination, 20% Coursework

Indicative reading

P. Cameron, Combinatorics, Topics, Techniques Algorithms, Cambridge Press, (1994)
L. Lovasz, J. Pelikan, and K. Vesztergombi, Discrete Mathematics: Elementary and Beyond. Springer-Verlag, (2003).
D. B. West, Introduction to Graph Theory, Prentice Hall, (1996).
R.J. Wilson, Introduction to Graph Theory, Fourth edition. Longman, Harlow, (1996).
In addition, for level 7 students:
J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Text in Math. 244, Springer-Verlag, (2008).
B. Ballobas, Modern Graph Theory, Graduate Text in Math., 184, Springer-Verlag, (1998).

See the library reading list for this module (Canterbury)

Learning outcomes

The intended subject specific learning outcomes. On successfully completing the level 6 module students will be able to:
1 demonstrate systematic understanding of key aspects of Graphs and Combinatorics;
2 demonstrate the capability to deploy established approaches accurately to analyse and solve problems using a reasonable level of skill in calculation and manipulation of the material in the following areas: trees, shortest paths problems, walks on graphs, graph colourings and embeddings, flows and matchings, matrices and graphs;
3 apply key aspects of Graphs and Combinatorics theory in well-defined contexts, showing judgement in the selection and application of tools and techniques.

The intended generic learning outcomes. On successfully completing the level 6 module students will be able to:
1 manage their own learning and make use of appropriate resources;
2 understand logical arguments, identifying the assumptions made and the conclusions drawn;
3 communicate straightforward arguments and conclusions reasonably accurately and clearly;
4 manage their time and use their organisational skills to plan and implement efficient and effective modes of working;
5 solve problems relating to qualitative and quantitative information;
6 make competent use of information technology skills such online resources (Moodle), internet communication);
7 communicate technical material competently;
8 demonstrate an increased level of skill in numeracy and computation;
9 demonstrate the acquisition of the study skills needed for continuing professional development.

University of Kent makes every effort to ensure that module information is accurate for the relevant academic session and to provide educational services as described. However, courses, services and other matters may be subject to change. Please read our full disclaimer.