more samples

…Topology     …Primes

Today, engineers use networks in many technologies, from high-speed internet service to oil pipelines. But 300 years ago, the idea of a network did not even exist.

The bridges of Königsberg

Mathematically, a network is very simple: a network of points or ‘nodes’, some of them joined by edges. The first person to recognize networks and apply mathematical reasoning to them was the great Swiss mathematician Leonhard Euler, who also did work in other fields ranging from number theory to modelling growth. He was working on a famous puzzle about the city of Königsberg (modern-day Kaliningrad, in Russia).

Look at the map. The red dots stand for the different parts of the city, as divided up by waterways. Can you make a tour of the city that crosses each bridge exactly once? Copy the map and try a few routes. Do any of them work? How many more routes do you think there might be?

Look at a single red dot or node, as Euler did. Suppose this node is neither the start nor the finish. You can cross the node more than once on your tour, but every time you enter, you need a different bridge, or edge, to leave by. What does this tell you about the number of edges touching the node? Hint: Think about odd and even numbers.

If the start and finish of your tour are at the same node, you can use the same reasoning as before for this node too. If they are different, you need one more or fewer “exit” than “entries” at these nodes.

So, to complete a trail,
• either every node must have an _____ number of edges
• or two nodes must have an _____ number of edges, and all the rest must have an _____ number

Look again at the map. Can you solve the bridges of Königsberg problem now?

How to colour a map

Here's a seemingly easy problem: take a map, and colour the countries so that no two neighbouring countries have the same colour. How many colours do you need?

These maps have been converted into networks. The networks show how many colours you need for each map. Are there any maps that need five colours?

Explore Ø Can a map be too complicated for three or four colours? Try working backwards from this pentagonal network, which needs five colours, to a map that matches it. Hint: Remember that the countries are the nodes, not the spaces in between.

What problems do you meet? Does this change your answer to the question above?

In over a century of looking, no one ever found a map that needed five colours. But it seemed impossible to be sure some super-complex map didn’t exist. Then, in 1975, Appel and Haken programmed a computer to break down all the possibilities into cases, and to check each case. A computer was needed because there were over 1900 cases!

The Appel-Haken program finally proved the long-guessed-at truth that four colours are enough for any map. But the proof is not beautiful, and as the poet John Keats said, ‘Beauty is truth, truth beauty.’ Network theorists still hope to find a shorter, more ‘elegant’ proof that you could write down by hand.

Take the Tube

Probably the most famous representation of a transport network is the London Underground (or “tube”) map. Back in 1931, Harry Beck devised the first version of this map. By 1936 he had

Click on this image to see it full size

realized that instead of a map that was geographically exact, passengers would rather use a plan that clearly showed the network of stations (nodes) and routes (edges). The map, which has become a design icon, also uses colour coding to show the different lines making up the Underground.

Running a system as complex as the London underground smoothly requires in-depth modelling of passenger flows at different times of the day and week. Flow modelling of all kinds are the most important applications of network theory in our ever more connected world.
 

Explore Ø How many different ways can you get from South Kensington to Kings Cross, without repeating any part of your route? Try some other pairs of stations. How could you determine an “average connectivity” for the London Underground?