MA4AGT-Applied Graph Theory

Module Provider: Mathematics and Statistics
Number of credits: 10 [5 ECTS credits]
Terms in which taught: Spring term module
Pre-requisites: MA1LIN Linear Algebra
Non-modular pre-requisites:
Modules excluded: MA3AGT Applied Graph Theory
Module version for: 2016/7

Module Convenor: Dr Danica Greetham


Summary module description:
This module is an introduction to graph theory, covering selected topics.

To provide an overview of the basic concepts in graph theory and to motivate interest in applications of graph theory to real-world network problems.

Assessable learning outcomes:
By the end of the course, students are expected to be able:
-to understand basic graph properties and how they are related to each other
-to construct proofs using techniques similar to those covered in lectures
-to recognise simple connections between spectral properties and the structure of graphs and to compute spectra of basic types of graphs
-to apply the probabilistic method in order to prove properties of almost all graphs
-to create and manipulate Python scripts for creation and analysis of different types of graphs
-to describe and evaluate one of the presented random graph models beyond material covered in lectures.

Additional outcomes:
Students should learn the basics of computational complexity (NP-completeness).

Outline content:
Introduction to computational complexity, Euler tours, connectivity, matching and covering, colouring, standard graph algorithms, basic properties of graph spectra, probabilistic method, properties of almost all graphs, models of random graphs.

Brief description of teaching and learning methods:
Lectures supported by problem sheets and PC practicals.

Contact hours:
  Autumn Spring Summer
Lectures 20
Tutorials 4
Guided independent study 76
Total hours by term 100.00
Total hours for module 100.00

Summative Assessment Methods:
Method Percentage
Written exam 70
Set exercise 30

Other information on summative assessment:
3 assignments.

Formative assessment methods:
Problem sheets.

Penalties for late submission:
The Module Convenor will apply the following penalties for work submitted late, in accordance with the University policy.

  • where the piece of work is submitted up to one calendar week after the original deadline (or any formally agreed extension to the deadline): 10% of the total marks available for the piece of work will be deducted from the mark for each working day (or part thereof) following the deadline up to a total of five working days;
  • where the piece of work is submitted more than five working days after the original deadline (or any formally agreed extension to the deadline): a mark of zero will be recorded.

  • The University policy statement on penalties for late submission can be found at:
    You are strongly advised to ensure that coursework is submitted by the relevant deadline. You should note that it is advisable to submit work in an unfinished state rather than to fail to submit any work.

    Length of examination:
    2 hours.

    Requirements for a pass:
    A mark of 50% overall

    Reassessment arrangements:
    One examination paper of 2 hours duration in August/September - the resit module mark will be the higher of the exam mark (100% exam) and the exam mark plus previous coursework marks (70% exam, 30% coursework).

    Additional Costs (specified where applicable):
    1) Required text books:
    2) Specialist equipment or materials:
    3) Specialist clothing, footwear or headgear:
    4) Printing and binding:
    5) Computers and devices with a particular specification:
    6) Travel, accommodation and subsistence:

    Last updated: 21 December 2016

    Things to do now