# Teacher package: Graphs and networks

Issue 52
September 2009

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 three 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.
• Graphic answers: Sometimes thinking of something in terms of a graph or network can help you solve difficult problems. These articles look at some examples.

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.

Helping business make a crust — Wireless security comes down to graph colourings.

Crime fighting maths — Using network theory to find out who contaminated the river.

### Network topology

Wiring up brains — The human brain faces a difficult trade-off. On the one hand it needs to be complex to ensure high performance, and on the other it needs to minimise "wiring cost". It's a problem well-known to computer scientists. And it seems that market driven human invention and natural selection have come up with similar solutions.

Neuro-tweets: #hashtagging the brain — As the article above reports, our brain has quite a lot in common with worm brains and information processing systems. But how does it compare to online social networks?

Network news — Scale free networks explain why the rich and famous tend to get more rich and more famous.

Open wide — Why open-source software is better than its closed counterpart, explained using networks.

Rap: rivalry and chivalry — The small world network of rap.

Networks: nasty and nice — How to disrupt scale free terrorist networks.

Catching terrorists with maths — This article contains a section on the small world network formed by the neurons in the brain.

Machine prose — A sophisticated analysis of the language network teaches machines to talk.