This package brings together all Plus content on graph and network theory. Graphs and networks turn up in many real-life problems, from neuroscience to telecommunications. To start off, you might like to read our brief overview article
From bridges to networks — How a cute 18th century puzzle laid the foundations for one of the most modern areas of maths: network theory. This article is also available as a poster which you can download and put on your wall.
We have divided all our other articles into three categories:
- Graphs and networks in-depth: These articles (and video) give a detailed account of questions relating to graphs and networks and their applications in science, life and other areas of maths.
- Social networks: Because everyone loves social networks — real and virtual —we have made a special category for them and the mathematical problems connected to them.
- Network news: This is a collection of news stories relating to networks and graphs and the role they play in the real world.
Our sister site NRICH has a beautiful collection of resources designed to give a gentle introduction to the world of graph theory and networks. You don't need any prior knowledge, so jump in, have a play, and see what you can discover!
Graphs and networks in-depth
Mathematical moments: Frank Kelly — In this video we talk to the mathematician Frank Kelly about his work developing mathematical models to understand large-scale networks.
Friends and strangers — This article uses graph colourings to find order in chaos.
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.
Maths aMazes — Finding your way out of mazes using graphs.
Crime fighting maths — Using network theory to find out who contaminated the river.
Euler's polyhedron formula — How networks help to pin down polyhedra.
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.
The graph isomorphism problem — How fast can you tell whether two networks are the same?
The Tower of Hanoi: Where maths meets psychology — Mathematicians and psychologists don't cross paths that often and when they do you wouldn't expect it to involve an (apparently) unassuming puzzle like the Tower of Hanoi. Yet, the puzzle holds fascination in both fields.
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.
Counting the trees of life — How many possible genetic relationships are there between a collection of different species? The answer is mind-bogglingly large.
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.
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.
Exploring the financial ecosystem — How models borrowed from biology, and a little network theory, are helping us to manage risk in financial markets .
Call routing in telephone networks — Finding optimal paths through a busy network.
Radio controlled? — This article shows how the mathematics of colouring graphs can help avoid interference on your mobile phone.
Social networks
Power networks — Why do so many networks exhibit a similar kind of structure? It's because the rich tend to get richer!
Have you heard: The maths of rumour spreading — Mathematical models predict how fast a rumour will spread through a social network and how many people it's likely to reach.
Big data — Everybody's talking about Big Data. But what exactly do they mean and what does it have to do with networks?
Climbing the Twitter ladder — How popular and successful are you? Not as much as your friends is the sad answer, at least as far as Twitter is concerned.
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.
Network news
Disease moves like ripples on a pond — Epidemiologists use complex 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?
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.
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.
Country road, take me home — This article looks at the famous road colouring problem.
Solving sudokus — Using graph colouring to solve sudokus.
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.
Helping business make a crust — Wireless security comes down to graph colourings.
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.
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?
Open wide — Why open-source software is better than its closed counterpart, explained using networks.
Machine prose — A sophisticated analysis of the language network teaches machines to talk.
Don't forget that our sister site NRICH has a beautiful collection of resources designed to give a gentle introduction to the world of graph theory and networks. You don't need any prior knowledge, so jump in, have a play, and see what you can discover!