## Teacher package: Graphs and networks

Submitted by plusadmin on September 1, 2009The *Plus* teacher packages are designed to give teachers and students (and everyone else) 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*. To start off, you might like to read our brief overview article

We have divided all our other 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

Maths in a minute: The bridges of Königsberg — This article looks at an problem with an ingenious solution that started off network theory. You can also watch Bridges of Königsberg: The movie.

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

The art gallery problem — How would you place guards in an art gallery to make sure nothing gets stolen? The answer comes from graph colouring.

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

Happy birthday, London Underground! — The famous London tube map is a so-called *topological map*. It illustrates an important idea in network theory: that two networks can be the same even though they look very different.

Power networks — Why do so many networks exhibit a similar kind of structure? It's because the rich tend to get richer!

Middle class problems — How quickly can you tell whether two apparently different networks are actually the same? It's a famous question in computer science and it appears to have come closer to an answer.

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

Exploring the financial ecosystem — How models borrowed from biology, and a little network theory, are helping us to manage risk in financial markets .

Disease moves like ripples on a pond — Epidemiologists usecomplex models to predict the spread of diseases. But is there a way to hide all this complexity and draw a simpler picture of how diseases spread, even in today's complex world?

Too big to write, but not too big for Graham — How a question about the complexity of networks gave rise to a number that's bigger than the observable Universe.

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.