GRAPHS AND NETWORKS - 2025/6

Module Overview

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, data science, 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.

Module provider

Mathematics & Physics

Module Leader

CHENG Bin (Maths & Phys)

Number of Credits: 15

ECTS Credits: 7.5

Framework: FHEQ Level 6

Module cap (Maximum number of students): N/A

Module Availability

Semester 2

Prerequisites / Co-requisites

None

Module content

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.


• Spectral methods: the adjacency and Laplacian matrices.


• Graph polynomials and colourings.


• Network route and flow optimisation problems.

Assessment pattern

Alternative Assessment

N/A

Assessment Strategy

The assessment strategy is designed to provide students with the opportunity to demonstrate: 

• That they have gained knowledge of 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:

• One in-semester test (50 minutes), worth 20% of the module mark, corresponding to Learning Outcomes 1 to 3.


• A synoptic examination (2 hours), worth 80% of the module mark, corresponding to Learning Outcomes 1 to 4. 

Formative assessment
There are two formative unassessed courseworks over an 11 week period, designed to consolidate student learning. 

Feedback
Students receive individual written feedback on the formative unassessed coursework and the in-semester test. The feedback is timed so that feedback from the first unassessed coursework assists students with preparation for the in-semester test. The feedback from both unassessed courseworks and the in-semester test assists students with preparation for the end-of-semester examination. This written feedback is complemented by verbal feedback given in letures. Students also receive verbal and written feedback in office hours.

 

Module aims

• 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.  

Learning outcomes

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:

• Three one-hour lectures per week for eleven weeks, with typeset notes to complement the lectures. The lectures provide a structured learning environment. Where appropriate, some of the lecture time will be treated as a tutorial, giving opportunities for students to ask questions and to practice methods taught.


• There are two unassessed courseworks to provide students with further opportunity to consolidate learning. Students receive individual written feedback on these as guidance on their progress and understanding.

Lectures may be recorded. Lecture recordings are intended to give students the opportunity to review parts of the session that they might not have understood fully and should not be seen as an alternative to attendance at lectures.

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.

Reading list

https://readinglists.surrey.ac.uk
Upon accessing the reading list, please search for the module using the module code: MAT3043

Other information

The School of Mathematics and Physics is committed to developing graduates with strengths in Digital Capabilities, Employability, Global and Cultural Capabilities, Resourcefulness and Resilience and Sustainability. This module is designed to allow students to develop knowledge, skills, and capabilities in the following areas:

Digital Capabilities: The SurreyLearn page for MAT3043 features a dynamic discussion forum where students can pose questions and engage with others using e.g. LaTeX and MathML tools. This enhances their digital competencies while facilitating collaborative learning and information sharing.

Employability: The diverse applications of material covered in MAT3043 underscores its significance in many employment types. In the life sciences, graph theory is used to model complex biological networks. In the physical sciences, it aids understanding of power grids in engineering. In the social sciences, it helps analyze social networks, transportation systems, and communication patterns. Additionally, in business, graph theory plays a pivotal role in supply chain optimization, route planning, and fraud detection, offering insights into efficient resource allocation and risk management.

Global and Cultural Capabilities: Students enrolled in MAT3043 originate from various countries and possess a wide range of cultural backgrounds. During problem solving sessions in lectures, student engagement in discussions naturally cultivates the sharing of different cultures.

Resourcefulness and Resilience: Through the abstract concepts and problem-solving tasks included in MAT3043, students learn to think critically, adapt to challenging situations, and persevere through setbacks. The problems and algorithms of graph theory nurture resourcefulness, and the intricacies teach resilience. These skills, honed through graph theory, transcend mathematics, equipping students with valuable tools for tackling the uncertainties and complexities of life, academic or otherwise.

Sustainability: An understanding of graph theory helps design more eco-friendly and resource-efficient solutions to practical problems. For instance, graph theory can be used to model and optimize energy distribution networks, reducing waste and environmental impact. Moreover, graph theory can help analyze the flow of goods and services, optimizing transportation routes and reducing emissions. Thus, MAT3043 equips students with the tools to address sustainability challenges.

Programmes this module appears in

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 2025/6 academic year.