Graphs and networks at the Tate Modern, London
The bridges of Königsberg
We are not the first people keen to go on mathematical tours of a city. As we start off on our mathematical walking tour of London, standing here on the banks of the Thames, let’s cast our minds back to another time and place, to Kaliningrad, a city in the Russian enclave between Poland and Lithuania, and to 1735 when that city was part of Prussia and was known as Königsberg.
Königsberg, like London, was divided by a river. The city was arranged on the north and south banks of the River Pregal, which widens to contains two islands. The banks were linked to the islands by seven beautiful bridges. The story goes that the intellectuals of the time liked to play a parlour game when they met in the coffee houses or salons: could you come up with a walking tour of the city of Königsberg that crossed each of the seven bridges once and only once. [Can you suggest a path they could have taken?].
Euler’s solution – a new map of the city
The people of Königsberg could not seem to come up with the winning route. But the mathematician, Leonhard Euler, was able to solve the puzzle.
In Euler’s new map he ignored the geography, the types or lengths of the bridges, and instead presented each piece of land as a circle linked by a line if they were joined by a bridge. With this new perspective Euler was able to quickly solve the problem: there is no route that crosses each bridge of Königsberg once and only once. [Does anyone know why?]
Euler’s new type of map is called a graph, which is simply a set of nodes (the pieces of land) that are connected by links (the bridges). Euler realised that a route that crosses each bridge exactly once is only possible if either exactly zero or two of the nodes have an odd number of links. And all the nodes on the graph of the bridges of Königsberg have an odd number of links – therefore there is no walking route that crosses each bridge once and only once. [Why is such a route possible only if either exactly 0 or 2 nodes have an odd number of links?]
This is because if you don’t want to get stuck on a piece of land on the way, each one has to have an in-bridge and and out-bridge, which would give it an even number of links. The only possible exception is that you end in a different place than you started, in which case the beginning and ending points have an odd number of links.
Graph theory and network science
It is very rare to pinpoint with precision the moment a new field of mathematics was born. But when Euler discovered this solution to the Bridges of Königsberg problem in 1735 he founded the field of graph theory. [Can anyone think of something else you could represent by a graph, a set of things that are linked together? What are the nodes? What are the links?]
Graphs are used to map any network, including those that criss cross our cities: transport networks of roads, train lines and bus routes; social networks of people linked by family and friendships; and power grids with buildings linked by power lines to power stations, such as the Bankside Power Station behind us, that now houses the Tate Modern art gallery.
Mathematically describing a network allows us to better understand how things can move around the network, for example how traffic flows around the city. Traffic congestion isn't just a modern problem. Albemarle Street became the first one-way street in London when horses and carriages caused traffic jams as crowds flocked to the science lectures at the Royal Institution in the nineteenth century.
Network science is hot topic of research and brings together many disciplines. Mathematical discoveries, made just in the last decade, are revolutionising the way we study the spread of diseases and altering the way we fight diseases such as AIDS.
Props: chalk, sweets, a dozen pieces of rope (each around a metre long), a small hoop to pass over the pieces of rope (a ring-shaped frisbee works well)
We've included questions (in italics in the description above) that you can ask the group to get them involved and a crib sheet below to suggest how to interweave the demos into your explanation.
Before you start the tour, chalk the layout of Königsberg and its bridges on the ground so that people can try out their walking route. If you put something on each bridge (a sweet is a good incentive!) they can keep track of their route by only crossing bridges that contain a sweet, collecting the sweets as they go.
Then you can draw out Euler’s graph alongside your city layout so that the group can see how the pieces of land correspond to the nodes and the bridges to the links. This diagram of the graph will also make your explanation of Euler's solution clearer.
Euler's solution demo
You might like to try out Euler's solution on a network created by the group. Ask 8 (or so) people to create a network by taking the ends of two or more of a dozen (or so) pieces of rope that are spread out between them. Then ask everyone to check how many pieces of rope they are holding – as long as all of them have an even number of ends, or exactly two of them have an odd number of ends, then Euler's solution says that you should be able to move through the network travelling over each link (piece of rope) exactly once. Try to navigate the resulting network (it works well to pass a small hoop over each piece of rope) placing each piece of rope down as you pass over it, therefore ensuring you only use each link once.
- Chalk out layout of bridges of konigsberg before hand
- Explain Bridges of Königsberg problem
- Bridges demo
- Explain Euler's solution, chalking out graph next to the bridges layout
- Euler's solution demo
- What is a graph, node and link
- Other examples of networks and impact of new understanding
See this Site in a Tour
The Tate Modern Gallery itself is open Sunday – Thursday, 10.00–18.00 and Friday and Saturday, 10.00–22.00. But the bankside area is open at all times.
Written by Rachel Thomas and Marcus du Sautoy, based on a an idea from Nick Simmonds
Image of old Konigsberg is in the public domain
Graph of bridges of Konigsberg found at http://en.wikipedia.org/wiki/File:Konigsburg_graph.svg / CC BY-SA 3.0
Photo of network demonstration by David White / CC BY-SA 3.0