Teacher package: Graphs and networks

The Plus teacher packages are designed to give teachers (and students) easy access to Plus content on a particular subject area. Most Plus articles go far beyond the explicit maths taught at school, while still being accessible to someone doing A level maths. They put classroom maths in context by explaining the bigger picture — they explore applications in the real world, find maths in unusual places, and delve into mathematical history and philosophy. We therefore hope that our teacher packages provide an ideal resource for students working on projects and teachers wanting to offer their students a deeper insight into the world of maths.

Graphs and networks

This teacher package brings together all Plus articles on graph and network theory. Graphs and networks turn up in many real-life problems, from neuroscience to telecommunications. In the UK curriculum, they make a frequent appearance in the area known as decision maths. There is a lot to choose from, so we have divided our articles into two categories:

• Algorithms: Many real-life problems involve finding a particular colouring of a graph or network, finding an optimal path or "flow" through a graph or network, or constructing graphs from given information. The articles in this category explore some of the algorithms that are used to solve these kind of problems.
• Network topology: Many real-life networks are extremely complex, so mathematicians try and get a grip on them by getting an overall picture of their structure. The articles in this category explore the techniques used, introducing concepts such as small world networks and scale free networks.

Don't forget that our sister site NRICH has many hands-on problems, activities and articles covering graph and network theory.

Algorithms

Friends and strangers — This article uses graph colourings to find order in chaos.

Radio controlled? — This article shows how the mathematics of colouring graphs can help avoid interference on your mobile phone.

Country road, take me home — This article looks at the famous road colouring problem.

Reconstructing the tree of life — Darwin's famous tree of life is of course a mathematical graph. This article looks at some of the mathematical problems facing phylogeneticists.

Solving sudokus — Using graph colouring to solve sudokus.

Maths aMazes — Finding your way out of mazes using graphs.

Call routing in telephone networks — Finding optimal paths through a busy network.

Rubik success in twenty-six steps — Using graph theory and group theory to show that you can solve a Rubik's cube in twenty-six moves — theoretically at least.

Euler's polyhedron formula — How networks help to pin down polyhedra.