England.

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

## Modules count towards OU qualifications

OU qualifications are modular in structure; the credits from this undergraduate module could count towards an honours degree.

## Module

MST368

### Credits

Credits

• Credits measure the student workload required for the successful completion of a module or qualification.
• One credit represents about 10 hours of study over the duration of the course.
• You are awarded credits after you have successfully completed a module.
• For example, if you study a 60-credit module and successfully pass it, you will be awarded 60 credits.
30

### Study level

Across the UK, there are two parallel frameworks for higher education qualifications, the Framework for Higher Education Qualifications in England, Northern Ireland and Wales (FHEQ) and the Scottish Credit and Qualifications Framework (SCQF). These define a hierarchy of levels and describe the achievement expected at each level. The information provided shows how OU module levels correspond to these frameworks.
Level of Study
OU SCQF FHEQ
3 10 6

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

## Teaching and assessment

• Marking your assignments (TMAs) and providing detailed feedback for you to improve.
• Guiding you to additional learning resources.
• Providing individual guidance, whether that’s for general study skills or specific module content.
• Facilitating online discussions between your fellow students, in the dedicated module and tutor group forums.

Module tutors also run online tutorials throughout the module. Where possible, recordings of online tutorials will be made available to students. While these tutorials won’t be compulsory for you to complete the module, you’re strongly encouraged to take part.

### Assessment

The assessment details for this module can be found in the facts box.

## Future availability

Graphs, games and designs (MST368) starts once a year – in October.

We expect it to start for the last time in October 2030.

## Regulations

As a student of The Open University, you should be aware of the content of the academic regulations which are available on our Student Policies and Regulations website.

### Course work includes:

6 Tutor-marked assignments (TMAs)
1 Interactive computer-marked assignment (iCMA)
Examination
No residential school

## Entry requirements

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.

## Preparatory work

You should be confident and fluent with the concepts covered in the diagnostic quiz and follow the advice.

The key topics to revise include:

• algebra
• matrices
• logical reasoning and proofs
• modular arithmetic.

## Register

Start End England fee Register
07 Oct 2023 Jun 2024 £1731.00

Registration closes 07/09/23 (places subject to availability)

This module is expected to start for the last time in October 2030.

### Study costs

There may be extra costs on top of the tuition fee, such as set books, a computer and internet access.

If your income is not more than £25,000 or you are in receipt of a qualifying benefit, you might be eligible for help with some of these costs after your module has started.

## Ways to pay for this module

### Open University Student Budget Account

The Open University Student Budget Accounts Ltd (OUSBA) offers a convenient 'pay as you go' option to pay your OU fees, which is a secure, quick and easy way to pay. Please note that The Open University works exclusively with OUSBA and is not able to offer you credit facilities from any other provider. All credit is subject to status and proof that you can afford the repayments.

You pay the OU through OUSBA in one of the following ways:

• Register now, pay later – OUSBA pays your module fee direct to the OU. You then repay OUSBA interest-free and in full just before your module starts. 0% APR representative. This option could give you the extra time you may need to secure the funding to repay OUSBA.
• Pay by instalments – OUSBA calculates your monthly fee and number of instalments based on the cost of the module you are studying. APR 5.1% representative.

#### Joint loan applications

If you feel you would be unable to obtain an OUSBA loan on your own due to credit history or affordability issues, OUSBA offers the option to apply for a joint loan application with a third party. For example, your husband, wife, partner, parent, sibling or friend. In such cases, OUSBA will be required to carry out additional affordability checks separately and/or collectively for both joint applicants who will be jointly and severally liable for loan repayments.

As additional affordability checks are required when processing joint loan applications, unfortunately, an instant decision cannot be given. On average the processing time for a joint loan application is five working days from receipt of the required documentation.

Studying with The Open University can boost your employability. OU courses are recognised and respected by employers for their excellence and the commitment they take to complete. They also value the skills that students learn and can apply in the workplace.

More than one in ten OU students are sponsored by their employer, and over 30,000 employers have used the OU to develop staff so far. If the module you’ve chosen is geared towards your job or developing your career, you could approach your employer to see if they will sponsor you by paying some or all of the fees.

• Your employer just needs to complete a simple form to confirm how much they will be paying and we will invoice them.
• You won’t need to get your employer to complete the form until after you’ve chosen your module.

### Credit/debit card

You can pay part or all of your tuition fees upfront with a debit or credit card when you register for each module.

We accept American Express, Mastercard, Visa and Visa Electron.

### Mixed payments

We know that sometimes you may want to combine payment options. For example, you may wish to pay part of your tuition fee with a debit card and pay the remainder in instalments through an Open University Student Budget Account (OUSBA).

Please note: your permanent address/domicile will affect your fee status and therefore the fees you are charged and any financial support available to you. The fee information provided here is valid for modules starting before 31 July 2024. Fees normally increase annually. For further information about the University's fee policy, visit our Fee Rules

This information was provided on 04/06/2023.

In order to qualify, you must:

1. be resident in England
2. have a personal income of less than £25,000 (or receive qualifying benefits)
3. have not completed one year or more on any full-time undergraduate programme at FHEQ level 4 or above, or completed 30 credits or more of OU study

Once you've started the registration process, either online or over the phone, we'll contact you about your payment options. This will include instructions on how you can apply to study for free if you are eligible.

If you're unsure if you meet the criteria to study for free, you can check with one of our friendly advisers on +44 (0)300 303 0069 or you can request a call back.

Don't worry! We offer a choice of flexible ways to help spread the cost of your Access module. The most popular options include:

• monthly payments through OUSBA
• part-time tuition fee loan (you'll need to be registered on a qualification for this option)

To explore all the options available to you, visit Fees and Funding.

## What's included

• a week-by-week study planner
• practice quizzes
• screencasts and online interactive demonstrations
• assessment details, instructions and guidance
• online tutorial access

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.

### Computing requirements

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 (11 'Big Sur' 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.

## If you have a disability

The OU strives to make all aspects of study accessible to everyone and this Accessibility Statement outlines what studying MST368 involves. You should use this information to inform your study preparations and any discussions with us about how we can meet your needs.