Graphs, games and designs
This module is about discrete mathematics and its applications to modelling and solving real-world problems. Applications include the famous Travelling Salesman Problem, assigning junior doctors to hospitals and storing/transmitting data resilient to errors. You’ll also see some recreational applications, e.g. how to always win at simple games and the mathematics of Sudoku. At the heart of all these problems is pure mathematics – in the form of graph theory, game theory, coding theory and design theory.
What you will study
We present the study material in a down-to-earth manner, with more emphasis on solving problems and applying algorithms than on abstract ideas and proofs.
The module comprises four books:
Book A: Graphs
Unit A1: Introduction to graphs
A graph is a collection of points, or vertices, joined by lines or edges; this unit gives a general introduction to these. We discuss Eulerian and Hamiltonian graphs and related problems; one of these is the well-known Königsberg bridges problem.
Unit A2: Trees
Trees are graphs occurring in areas such as branching processes, decision procedures and the representation of molecules. We discuss their mathematical properties, and their applications such as to the minimum connector problem and the travelling salesman problem.
Unit A3: Planarity and colouring
When can a graph be drawn in the plane without crossings? Is it possible to colour the countries of any map with just four colours so neighbouring countries have different colours? These are two of several apparently unrelated problems considered in this unit.
Book B: Networks
Unit B1: Network flows
This unit is concerned with connectivity in graphs and digraphs. For example, what is the maximum amount of a commodity (gas, water, passengers) that can pass between two points of a network in a given time?
Unit B2: Optimal paths, packing and scheduling
How do you plan a complex engineering project encompassing many activities? This application of graph theory is called ‘critical path planning’.
Unit B3: Matchings and assignment
If there are ten applicants for ten jobs and each is suitable for only a few jobs, is it possible to fill all the jobs? This unit considers problems where we must ‘pair off’ people or objects from two distinct groups, subject to certain constraints.
Book C: Games
Unit C1: Introduction to games
You’ll learn the basics of game theory and take a closer look at strategies to win some recreational games, such as Nim.
Unit C2: Zero-sum games
Here you’ll study games where what one player wins equals what the other loses. The main result is von Neumann’s theorem, which tells us there is always a solution to such games.
Unit C3: General games and Nash equilibria
We consider how to solve games in general, using an idea called Nash equilibrium. We look at applications to topics such as evolutionary biology and economics.
Book D: Designs
Unit D1: Latin squares
Sudoku is an internationally popular puzzle. A completed Sudoku is an example of a Latin square, and this unit discovers the mathematics behind these arrays of symbols.
Unit D2: Error-correcting codes
When we send a message through a system where errors or interference can occur, how do we ensure that the recipient receives the same message we sent? Solving this problem is the topic of coding theory.
Unit D3: Block designs
If an agricultural research station wants to test different crop varieties, how should they arrange the crops to minimise bias due to variations (for example, in the soil and sunlight)? The answer lies in the study of block designs.
You can find the full content list on the Open mathematics and statistics website.
There are no formal entry requirements to study this module.
However, you’ll need appropriate knowledge of mathematics. You’d normally prepare by having passed:
Or their engineering equivalents, plus OU level 2 study.
Are you ready for MST368?
You should be confident and fluent with the concepts covered in the diagnostic quiz and follow the advice.
The key topics to revise include:
- logical reasoning and proofs
- modular arithmetic.
You’ll have access to a module website, which includes:
- a week-by-week study planner
- practice quizzes
- screencasts and online interactive demonstrations
- assessment details, instructions and guidance
- online tutorial access
- access to student and tutor group forums.
We provide printed books covering the module content, including explanations, examples and activities to aid your understanding of the concepts and associated skills and techniques. We also provide a printed handbook.
You’ll need broadband internet access and a desktop or laptop computer with an up-to-date version of Windows (10 or 11) or macOS Monterey or higher.
Any additional software will be provided or is generally freely available.
To join in spoken conversations in tutorials, we recommend a wired headset (headphones/earphones with a built-in microphone).
Our module websites comply with web standards, and any modern browser is suitable for most activities.
Our OU Study mobile app will operate on all current, supported versions of Android and iOS. It’s not available on Kindle.
It’s also possible to access some module materials on a mobile phone, tablet device or Chromebook. However, as you may be asked to install additional software or use certain applications, you’ll also require a desktop or laptop, as described above.