GRAPHS AND NETWORKS - 2021/2
Module code: MAT3043
Graph theory is an aesthetically appealing branch of pure mathematics with strong links to other areas of mathematics (combinatorics, algebra, topology, probability, optimisation and numerics) and well developed applications to a wide range of other disciplines (including operations research, chemistry, systems biology, statistical mechanics and quantum field theory). This module provides an introduction to graph theory. There is an emphasis on theorems and proofs.
CHENG Bin (Physics)
Number of Credits: 15
ECTS Credits: 7.5
Framework: FHEQ Level 6
JACs code: G150
Module cap (Maximum number of students): N/A
Overall student workload
Independent Learning Hours: 106
Seminar Hours: 11
Guided Learning: 11
Captured Content: 22
Prerequisites / Co-requisites
Indicative content includes:
- The language of graph theory;
- Elementary results on paths, cycles, trees, cut-sets, Hamiltonian and Eulerian graphs;
- Examples from enumerative theory, including Cayley’s theorem on trees;
- Graphs embedded in surfaces; the genus of a graph;
- Spectral methods: the adjacency and Laplacian matrices;
- Graph polynomials, colourings and Ising / Potts models;
- Network route and flow optimisation problems;
- Applications to Markov chains and decision processes;
- Introduction to flux balance and related methods in systems biology;
- Examples and properties of small world and scale free networks.
|Assessment type||Unit of assessment||Weighting|
|Online Scheduled Summative Class Test||ONLINE TEST||20|
|Examination Online||ONLINE EXAM||80|
The assessment strategy is designed to provide students with the opportunity to demonstrate:
That they have learned the basic material in the field, and are able to apply it to examples and problems.
Thus, the summative assessment for this module consists of:
In-semester test. Constitutes 20% of the final mark.
Final Examination, 2 hours, end of Semester. Constitutes 80% of final mark.
Formative assessment and feedback
Students will receive verbal feedback in tutorials. There will also be unassessed coursework on which students will receive written feedback
- This module aims to provide an introduction to graph theory, motivated and illustrated by applications to the life, physical and social sciences and to business.
|1||Demonstrate understanding of the language and proof techniques used in elementary graph theory||KC|
|2||Apply methods from combinatorics, linear algebra and topology to graphs||KCT|
|3||Apply graph theoretical methods and techniques to network optimisation problems;||CT|
|4||Demonstrate an elementary knowledge of a range of applications of graph theory to the life, physical and social sciences and to business.||CPT|
C - Cognitive/analytical
K - Subject knowledge
T - Transferable skills
P - Professional/Practical skills
Methods of Teaching / Learning
The learning and teaching strategy is designed to:
Equip students with the knowledge, practical experience and confidence to apply the techniques of Graph Theory to abstract and practical problems.
The learning and teaching methods include:
3 hours of lectures and tutorials per week for 11 weeks. Learning takes place through lectures, tutorials, exercises, coursework, tests and background reading.
Indicated Lecture Hours (which may also include seminars, tutorials, workshops and other contact time) are approximate and may include in-class tests where one or more of these are an assessment on the module. In-class tests are scheduled/organised separately to taught content and will be published on to student personal timetables, where they apply to taken modules, as soon as they are finalised by central administration. This will usually be after the initial publication of the teaching timetable for the relevant semester.
Upon accessing the reading list, please search for the module using the module code: MAT3043
Programmes this module appears in
|Mathematics MMath||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics with Statistics MMath||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics with Statistics BSc (Hons)||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics BSc (Hons)||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Financial Mathematics BSc (Hons)||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics with Music BSc (Hons)||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics MSc||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics and Physics BSc (Hons)||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics and Physics MPhys||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
|Mathematics and Physics MMath||2||Optional||A weighted aggregate mark of 40% is required to pass the module|
Please note that the information detailed within this record is accurate at the time of publishing and may be subject to change. This record contains information for the most up to date version of the programme / module for the 2021/2 academic year.