# Teacher package: Graphs and networks

Issue 52The *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.

### Graphic answers

Mathematicians rival octopus in World Cup final prediction — A mathematical analysis of team tactics predicted a Spanish win in the last FIFA World Cup final and also shed some light on why England were trashed by Germany.

Biology's next microscope, mathematics' next physics — It is thought that the next great advances in biology and medicine will be discovered with mathematics. This article looks at an example of how graph theory can help with a problem in genetics.

Picking holes in mathematics — The logician Kurt Gödel showed that if you set out proper rules for mathematics, you lose the ability to decide whether certain statements are true or false. At first, the *undecidable* problems mathematicians came up with were rather esoteric, but some more concrete examples, including one from graph theory, have now been found.

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