This module is about using ideas from discrete mathematics to model problems, and representing these ideas through diagrams. The word 'graphs' refers to diagrams consisting of points joined by lines. These points may correspond to chemical atoms, towns, electrical terminals or anything that can be connected in pairs. The lines may be chemical bonds, roads, wires or other connections. The main topics of mathematical interest are graphs and digraphs; network flows; block designs; geometry; codes; and mathematical modelling. Application areas covered include communications; structures and mechanisms; electrical networks; transport systems; social networks; and computer science. To study this module you should have a sound knowledge of relevant mathematics provided by the appropriate OU level 2 study.
Course facts | |
---|---|
About this course: | |
Course code | MT365 |
Credits | 30 |
OU Level | 3 |
SCQF level | 10 |
FHEQ level | 6 |
Course work includes: | |
4 Tutor-marked assignments (TMAs) | |
4 Interactive computer-marked assignments (iCMAs) | |
Examination | |
No residential school |
What codes are used by spacecraft in communicating with Earth? Where do you brace a framework to make it rigid? How many colours are needed for a map to ensure that neighbouring countries have different colours? How can you assign people to jobs for which they are qualified? These are some of the questions to be answered in the module. The problems range from those arising in technology, operational research and the sciences to puzzles of a recreational nature. We show the connections between problems in widely differing areas and describe methods for their solution that use the properties they have in common.
The material is presented in a down-to-earth manner, with the emphasis on solving problems and applying algorithms, rather than on abstract ideas and proofs.
The module is divided into three related areas: graphs, networks and design. The Introduction introduces two themes of the module, combinatorics and mathematical modelling, and illustrates them with examples from the three areas.
Graphs 1: Graphs and digraphs discusses graphs and digraphs in general, and describes the use of graph theory in genetics, ecology and music, and of digraphs in the social sciences. We discuss Eulerian and Hamiltonian graphs and related problems; one of these is the well-known Königsberg bridges problem.
Networks 1: Network flows is concerned with the problem of finding the maximum amount of a commodity (gas, water, passengers) that can pass between two points of a network in a given time. We give an algorithm for solving this problem, and discuss important variations that frequently arise in practice.
Design 1: Geometric design, concerned with geometric configurations, discusses two-dimensional patterns such as tiling patterns, and the construction and properties of regular and semi-regular tilings, and of polyominoes and polyhedra.
Graphs 2: Trees Trees are graphs occurring in areas such as branching processes, decision procedures and the representation of molecules. After discussing their mathematical properties we look at their applications, such as the minimum connector problem and the travelling salesman problem.
Networks 2: Optimal paths How does an engineering manager plan a complex project encompassing many activities? This application of graph theory is called 'critical path planning'. It is one of the class of problems in which the shortest or longest paths in a graph or digraph must be found.
Design 2: Kinematic design The mechanical design of table lamps, robot manipulators, car suspension systems, space-frame structures and other artefacts depends on the interconnection of systems of rigid bodies. This unit discusses the contribution of combinatorial ideas to this area of engineering design.
Graphs 3: 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 that neighbouring countries have different colours? These are two of several apparently unrelated problems considered in this unit.
Networks 3: Assignment and transportation 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? If a manufacturer supplies several warehouses with a product made in several factories, how can the warehouses be supplied at the least cost? These problems of the system-management type are answered in this unit.
Design 3: Design of codes Redundant information in a communication system can be used to overcome problems of imperfect reception. This section discusses the properties of certain codes that arise in practice, in particular cyclic codes and Hamming codes, and some codes used in space probes.
Graphs 4: Graphs and computing describes some important uses of graphs in computer science, such as depth-first and breadth-first search, quad trees, and the knapsack and travelling salesman problems.
Networks 4: Physical networks Graph theory provides a unifying method for studying the current through an electrical network or water flow through pipes. This unit describes the graphical representation of such networks.
Design 4: Block designs If an agricultural research station wants to test different varieties of a crop, how can a field be designed to minimise bias due to variations in the soil? The answer lies in block designs. This unit explains the concepts of balanced and resolvable designs and gives methods for constructing block designs.
Conclusion In this unit, many of the ideas and problems encountered in the module are reviewed, showing how they can be generalised and extended, and the progress made in finding solutions is discussed.
Successful study of this module should enhance your skills in finding solutions to problems, interpreting mathematical results in real-world terms and communicating mathematical ideas clearly to both experts and non-experts.
There are no formal entry requirements.
You need pre-requisite mathematical skills and knowledge: familiarity algebraic manipulation and the idea of proof, and experience of matrix multiplication would be an advantage – check you're ready for MT365 with our self-assessed quiz.
You'd normally be prepared by completing OU level 1 and 2 study as part of one of our qualifications in mathematics, science or technology. For this module, we recommend that you've passed Essential mathematics 1 (MST124), Essential mathematics 2 (MST125) and 60 credits at OU level 2 in mathematics, science or technology.
If you're not sure you're ready, talk to an adviser.
The many diagrams in the text and the computing element could be demanding if you have impaired sight or certain types of colour blindness. Written transcripts are available for the audio-visual material.
To use the module software you will need to spend considerable amounts of time using a personal computer although its use is not essential. It is designed to enhance the student's learning experience but it is possible to pass the module without using it.
Module books, CDs, DVDs, software and a website.
CD player and DVD player (or computer able to play DVDs).
You require access to the internet at least once a week during the module to download module resources and assignments, submit assignments and to keep up to date with module news.
You will need a device with internet access to study this module as a web browser is used to access learning materials and activities. Any other computer-based activities you will need to carry out, such as word processing, using spreadsheets, taking part in online forums, and submitting files to the university for assessment, are specified in the module materials. If any additional software is needed for these tasks it will either be provided or is freely available. This module requires the installation of software from a hardware device e.g. DVD drive or USB stick. You may need administrative privileges to install software required for this module. Windows 10 S is not suitable as it restricts software installation to software available in the Windows Application Store.
A Windows desktop or laptop running Windows 7 or later operating system is suitable for this module. This module requires installation of Microsoft Windows specific software.
Some software will not run on Mac OS X, Linux, iOS or Android devices.
A netbook, tablet, phone, Mac or Linux computer that supports one of the browsers below may be suitable for some activities. However, these devices may not be suitable for one or more activities within this module. If you intend to use one of these devices please ensure you have access to another suitable desktop or laptop device that uses the Windows operating system so that you can carry out all activities on your mobile device. You will need a broadband internet connection to complete this module. Better video performance is available with higher connection speeds.
Recent versions of the following browsers for carrying out web-based activities:
Using company or library computers may prevent you accessing some internet materials or installing additional software.
To be able to talk and listen in our online discussions you will need both a microphone and speakers/headphones.
Devices with small screens may make it difficult to view the material provided and carry out the activities. However, a device that has a resolution of at least 1024 pixels horizontally and also at least 768 pixels vertically should be adequate.
See our Skills for OU study website for further information about computing skills for study and educational deals for buying Microsoft Office software.
You will have a tutor who will help you with the study material and mark and comment on your written work, and whom you can ask for advice and guidance. We may also be able to offer group tutorials or day schools that you are encouraged, but not obliged, to attend. Where your tutorials are held will depend on the distribution of students taking the module.
Contact us if you want to know more about study with The Open University before you register.
The assessment details for this module can be found in the facts box above.
You can choose whether to submit your tutor-marked assignments (TMAs) on paper or online through the eTMA system. You may want to use the eTMA system for some of your assignments but submit on paper for others. This is entirely your choice.
The details given here are for the module that starts in October 2017. It starts once a year – in October.
This course is expected to start for the last time in October 2022.
This module may help you to gain membership of the Institute of Mathematics and its Applications (IMA). For further information, see the IMA website.