MA4056 - Graph Theory (2023/24)
| Module specification | Module approved to run in 2023/24 | ||||||||||||
| Module title | Graph Theory | ||||||||||||
| Module level | Certificate (04) | ||||||||||||
| Credit rating for module | 15 | ||||||||||||
| School | School of Computing and Digital Media | ||||||||||||
| Total study hours | 150 | ||||||||||||
|
|||||||||||||
| Assessment components |
|
||||||||||||
| Running in 2023/24(Please note that module timeslots are subject to change) |
|
Module summary
In this module, we introduce the basic concepts of graph theory, focusing on finite graphs. These include numerical invariants of graphs and methods for calculating them; how to navigate through graphs (including the method that lies behind the resolution of the Königsberg problem discussed above); vertex and edge colourings of graphs and other numerical invariants of graphs; the conditions under which a graph is planar.
Prior learning requirements
None.
Available for Study Abroad? NO
Syllabus
• Definitions, adjacency and incidence matrices.
• Particular graphs, graphic sequences, walks, paths, trails, cycles.
• Disconnecting sets, separating sets, edge-connectivity, vertex connectivity.
• Counting walks, Eulerian graphs, Hamiltonian graphs.
• Planar graphs - Euler’s formula, Kuratowski’s theorem, dual graphs.
• Vertex colourings, Chromatic number and Chromatic polynomials.
Balance of independent study and scheduled teaching activity
This module will be delivered through a mixture of lectures and tutorials. The lectures will develop theory, explain the methods and techniques and demonstrate them by going through examples. The tutorials will provide students with the opportunity of reviewing their lecture notes and working through the problems designed for their practice, which will underpin the skills and techniques demonstrated in the lectures. Students will be encouraged to construct valid and precise mathematical arguments and will be expected to produce solutions using appropriate notational and stylistic conventions. Self-study exercises will enable students to monitor their own progress.
A set of lecture notes will be provided to students and answers for exercise questions will be put on the VLE.
Blended learning is incorporated by using online resources as a medium for communication (both peer and tutor-led) and will also provide additional materials to stimulate the student interest and broaden their horizons.
Learning outcomes
After successful completion of this module students should:
LO1: Be able to represent graphs in different forms and identify the main properties of given graphs and be able to interpret and evaluate the outcomes of algorithms.
LO2: Be able to count walks, trails, paths in a given graph and determine whether graphs are Eulerian/Hamiltonian etc.
LO3: Be able to apply Euler’s formula and related results to determine whether a graph is planar or not.
LO4: Be able to determine chromatic polynomial and chromatic number of a given graph.
Assessment strategy
The assessment for this module consists of a test and an exam.
There will be a progression test covering LO3, LO4 which will give students opportunity to demonstrate their understanding of selection of topics.
The final assessment will be an exam where students will be tested on LO4.
Bibliography
Core Text:
R.J.Wilson(1996), Introduction to Graph Theory (4-th edition) Longman
Recommended Reading:
M.Behzad, G.Chartrand, L.Lesniak-Forster(1996), Graphs and Digraphs, CRC Press
A.Dolan, J.Aldous(1993), Networks and Algorithms, Wiley
G.Chartrand, O.R.Oellermann(1993), Applied and Algorithmic Graph Theory, McGraw-Hill