June 2000: Maths Connects
(click on the image for larger version)
So, did you get the answer?
The circular network in the poster is part of the central region of the London Underground map, with the Circle Line turned into a real circle!
The station at the very centre of the map is Oxford Circus at the crossing-point between the red Central Line (between Notting Hill Gate (NH) and Bank/Monument (B/M)) and the light blue Victoria Line (between King's Cross (KC) and Victoria (V)). See if you can identify all of the stations and see which parts of the London Underground map we've included in our picture. Remember that we've concentrated on how the different stations are connected together, rather than where they would be on a `true' map.
The traditional London Underground map does not show the stations in their true (geographical) positions, but instead shows the underground network with the lines simplified, to make the diagram easier to read. This works because, from the point of view of navigating your way through the network, it's sometimes the way that things are connected that's important, not where they really are.
It turns out that to travel between any two of the stations in the diagram needs only one change of lines. It's possible to see why this is so by looking at the diagram - can you see how to prove it? (This isn't easy, but takes at least a few minutes' thought!)
Notice that we managed to draw the piece of the network that we have included in our picture without any of the lines crossing each other, except at stations. This kind of network is called planar (meaning flat). To do this, for example, we moved Euston station inside the circle of the Circle Line (it's just outside it on the "normal" map of the Undergound), but were careful to ensure that it stayed connected in the right way to the other stations.
Maybe you can figure out what the other stations in the picture are?
Networks (and the mathematics of networks) are becoming increasingly important in everyday life. Finding the fastest way to route information through networks such as the internet is now of major importance.
If you are reading this page on the internet, then did you realise that the information contained here was first broken down into smaller pieces, called packets; these packets have each journeyed through a complicated network of computers and switching devices before arriving at your computer, where they have been put back together (in the correct order!), forming the page that you now see.
Different parts of the internet are able to carry messages at different speeds (at different times), so it's important that packets of information can be re-routed around bottlenecks in the system to make sure they reach their destination on time. The computers which control the internet make thousands (even millions) of decisions about how to route packets every second. (If you've ever sat in a traffic jam and thought about trying to cut down a side-street to avoid it, the problems involved for the internet are not so different in many ways.)
In the top right-hand corner of the poster (and shown above) is another small network, showing all 24 ways of arranging the numbers 1, 2, 3, 4. Can you see what simple rule determines when two arrangements in the network are connected, and when they are not?
The mathematics of Networks is connected with that of Mazes, such as the one shown at the lower-right of the poster. Chris Budd and Chris Sangwin, from the University of Bath, show us some of the fascinating connections between networks and mazes and how the theory of networks can help us to simplify mazes and solve them...
C J Budd and C J Sangwin
Department of Mathematical Sciences, University of Bath.
If you look carefully you will notice a maze on the right hand side of the poster. In this article we would like to explain why the maze appears here and how mazes and networks have much in common. In fact the study of mazes and labyrinths takes us into the dark territory of murder, suicide, adultery, passion, intrigue, religion and conquest as we shall soon see...
The story of the Minotaur
Mazes are very ancient and appear many times in history. According to ancient legend, Daedalus constructed the so called `Cretan Labyrinth' in Knossos, to house the legendary Minotaur. The Minotaur was a fearsome creature, half man and half bull killed by Theseus in the famous legend in which he escapes using a ball of string provided by Ariadne.
Although we don't have direct evidence in the form of buried walls for the shape of the Cretan Labyrinth, there is a traditional idea about its shape, and a very nice geometrical construction for drawing one. This gives us our first link between mathematics and mazes. You can draw this on paper, or if you are on a beach it looks very good drawn into the sand with the help of a stick. To draw a traditional Cretan Labyrinth, start with the following cross and dots.
The following picture shows you how to complete the Cretan Labyrinth. Notice that the when you connect the lines you alternate left and right round the square. Now you can complete the picture.
Click here to see an animated JAVA version.
Try following the route from the entrance to the centre. This path is surprisingly long and in a full size labyrinth it would have taken some time to get to the centre. However, there is a further surprise in store. Although the path to the centre is very long there is only one way in and one way out! Theseus had to make no difficult decisions at all on his way to kill the Minotaur. Indeed, it was easy with this design to get to the centre and just as easy to get out again. In short there was no need for threads, Ariadne, broken hearts, suicide or any of the other features of the story.
Exactly the same geometric pattern as the Cretan Labyrinth appears in many different cultures and it is quite a common artistic image. Examples of similar mazes have been found scratched into caves in Cornwall (possibly by visiting Phonecian sea farers or by visiting mathematicians in a moment of boredom), on Roman coins and in pictures drawn by native American Indians. The pattern is of interest to mathematicians because it packs a very long path into a small space.
Using other seeds
Using different seeds (or starting shapes) when drawing the maze leads to different labyrinths. An important feature of the Cretan Labyrinth is that there is only one entrance and only one route toward the centre. We can ask the (mathematical) question of whether all seeds lead to Labyrinths with one entrance and route.
Although the Cretan maze is the most common, and probably the oldest, there are lots of others that we can draw. Let's try a different seed such as this one:-
To draw the complete picture remember to alternate drawing the lines from left to right. The resulting maze in this case looks like this,
The Rise of the Maze
The term Labyrinth is now generally means a construction that leads you from a starting point to a goal by taking you on a tortuous path, but requires no actual decisions. Your whole path is predetermined by the builder of the Labyrinth. Sacred sites were sometimes constructed as labyrinths by people who believed in the action of fate giving you an ultimate destiny which was entirely beyond control. However, following the Christianisation of the Roman Empire, and the belief in the action of free will, a different form of construction came into being. This was the maze.
In a maze intrepid travellers had to make a series of decisions, and their ultimate fates (in particular whether they reached the centre) relied upon the results of those decisions. Mazes were often built into the floors of churches and you were supposed to pray as you found your way towards the centre. The idea of the puzzle maze was developed during the Middle Ages and later into the celebrated hedge maze, often found in the grounds of stately homes.
The modern use of the hedge maze is now purely recreational. The puzzle is usually to find your way to the centre (and out again) starting from the entrance. Many mazes around the world are open to the public and make a great day out. Examples include the Jubilee Maze Centre at Symonds Yat (which has a fine museum of mazes at its centre), and the maze at Longleat, which has bridges and changes its pathways during the day. If you get lost in this maze then clues are available.
Perhaps the most famous public maze in England is the hedge maze at Hampton Court near London, which was constructed in 1690 AD and is still open to the public. If you get the chance, visit the maze at Hampton Court and indeed Hampton Court itself.
We hope that you are convinced that mazes are both fun and important. Now let's think how, as mathematicians, we could try to solve the puzzle of how to get to the centre of a maze (and out again) quickly and reliably.
Mazes and Networks
Next we will explain the link between mazes and networks. In fact we will transform a maze into a network. The result will look very different but the transformation will help us solve the problem of getting to the centre of a maze and then back out again. By doing this we will employ a very useful technique in mathematics;
Transform a hard problem into a simpler one which we can solve more easily.
How to walk round mazes and networks
The point we are trying to reach in a maze is called the centre of the maze. Some mazes can be solved by putting one hand on the hedge and following it round. Unfortunately this doesn't always work. In this section we will show how to transform a maze into a network and give a method for walking round networks which is guaranteed to find the centre. If we've transformed a maze into a network this then solves our problem of finding the way to the centre of the maze. We have chosen the point `M' in our maze. This is where network topology comes in and we will use these ideas to simplify the maze to its essential components.
When you go round a maze it doesn't matter how much you twist and turn, all that does matter are points where you have to make decisions. In a Cretan Labyrinth you don't have to decide anything at all, as once you enter the labyrinth you simply keep walking until you reach the centre. The centre point, the place we are trying to get to, is labeled M. We've put a decision point at the start as you can always decide not to enter the maze.
To simplify the maze we draw a network. In this network we write down all of the decision points as points on a piece of paper. We now draw paths from each of these points to the others, but only if you can go from one to another in the maze without having to make a decision in between. This gives you a network. Here is the maze with all the decision points marked.
Here is the completed network for the maze:
In contrast, here is the network of the Cretan Labyrinth. The only decision points are at the beginning and the end:
Using the network it is MUCH easier to see how to solve the maze. Indeed, we can label the solution just in terms of the decision points that you go through. For the Cretan Labyrinth this gives A -> B. For the more complicated maze one route to the centre is A -> B -> D -> K -> I -> M.
You should be able to find many more routes to the centre using this diagram. How many do you think there are?
The trick of reducing the maze to its bare essentials by finding a diagram which contains all of the information in the maze, is widely used in mathematics. A good example of this is the map of an underground railway system or metro. Often these maps only show the railway lines, stations and interconnections. Distances between stations on the ground do not always correspond to distances on a map. But do travellers on the train care?
Perhaps not, as they often only need to know how to get between stations. In fact, stripping away the unnecessary information might actually help then navigate successfully.
When we think in terms of networks, the problem of solving a maze becomes the following:
Can you find a route in the network which takes you from the beginning to the centre and then back again?
It is worth saying that there are really two different problems here. One is to find the route when you don't have a map of the maze to hand. This is the case in most recreational mazes. The second is to find the route when you do have a map. This case would arise if you were (for example) trying to find your way around a road network or a telephone exchange (or indeed the Underground).
We will consider the case when we don't have a map available.
In a network the decision points are called nodes and the lines connecting nodes are called edges or paths. Given a map of a network, the spaces left between the edges and the space outside are called the faces. If an odd number of paths meet at a node then it is called an odd node and if an even number of paths meet then it is called an even node. A dead end (such as the decision point at C) is an odd node as only one path leads into it.
Networks were first studied by the great Swiss mathematician Leonard Euler. Euler was one of the most productive mathematicians who ever lived and he created a lot of modern mathematics. In 1736 Euler became interested in networks through trying to solve the problem of the Bridges of Königsberg. Königsberg, now called Kaliningrad, is a town in Russia on the Baltic Sea which has the river Pregel running through it with the island of Kneiphof in the middle of the river. The mainland and the island were connected by bridges in the arrangement shown below:
The citizens of Königsberg had noticed that there seemed to be no way of going for a walk in which each bridge was crossed once and once only, but wondered whether they were being stupid and that there might be a route if only they looked hard enough. Euler took up this challenge and started by reducing the problem to a network. In this network, the nodes were the four land masses A, B, C, D and the edges were the bridges. Here is the resulting network:
The problem of the bridges of Königsberg can now be stated as follows:
Can you start from any node and construct a route around the network which will bring you back to the node and go down each path once and only once?
It is possible to ask this question for any network, not just for the one above and Euler came up with a brilliant solution to the general problem. Here it is:
- If you have any network which has only even nodes then you can start at any node and find a route which returns you to that node which goes down each path once and once only.
- If the network has exactly two odd nodes then you can construct a route which starts at one odd node and ends up at the other and goes through every path once and once only.
- If the network has more than two odd nodes then there is no route that goes through every path once and once only.
It is worth pointing out that no network can have only one (or indeed any odd number) of odd nodes. The network for the bridges of Königsberg has four odd nodes so no route is possible which crosses over every bridge once and once only. To make this possible the simplest solution is to demolish the bridge between A and C, then at least you can walk from B to D going over each bridge once and only once (although you can't do this if you want to start and finish in the same place). This is a neat solution mathematically, not a great idea if you happen to live in Königsberg.
We seem to have come a long way from solving a maze, but in fact we have nearly finished. The proof of Euler's theorem actually gives us a way of solving the maze. What we do is use the methods described in the proof to construct a route into the centre of the maze and back out again which goes down each path at most twice. To start we first take the network for the maze. Now, these networks have a collection of odd and even nodes and this makes it awkward to use any of the results of the above theorem. Our first step is to convert the maze into one with only even nodes. This we do by the simple process of drawing each path between two nodes twice. What this means on the ground is that in following our way around the maze we are allowed to take each path twice but no more. Think about this - this is very necessary. If we could only go down each path once then there would be no way out of a dead end! For our example maze this gives the following network:
Doubling up the number of paths in the network corresponding to our maze has converted it into a network with only even nodes. Euler's first result states that in such a network we can construct a path from any node which will return us to that node and which goes down each path once and once only. Now, suppose that we start at the entrance to the maze at point A and find this route. As it goes down every path, sooner or later it will go down a path which leads to the centre of the maze. This is a splendid start. Now continuing along our route we will eventually get back to the start of the maze again. It looks as though we have found a foolproof way of cracking the maze. What is the catch? Well there isn't one really, except that the route we construct may not be optimal (ie. it may be much longer than the shortest route into the centre and back). This makes the method inefficient for solving problems concerned with traffic flow (for which there are much better methods around) but it doesn't matter too much for the networks corresponding to mazes.
As we have not given the proof of Euler's theorem, we can't immediately jump to solution. Fortunately this has already been done for us and we will describe the method of M. Trèmaux, which is described in the book ``Mathematical Recreations and Essays'' by Rouse Ball. What is nice about the method we are going to describe is that you don't need to use a map of the maze, but you do need to use a packet of peanuts and a bag of crisps.
How to solve a maze using a packet of peanuts and a bag of crisps
You enter the maze, which we will assume has high hedges which you can't see over, and that all paths and nodes (where you make decisions) look very much the same. The peanuts and crisps are used as markers in the maze. Trail the peanuts (here and there) as you go and leave a peanut at all decision points. This will tell you whether you have been to a decision point before or whether you have gone down a path before (without being too ecologically unfriendly). If you go down a path a second time, then trail a path of crisps. If you have a rule that you never go down a path with crisps this will stop you going down that path again. If you reach a decision point which does not have a peanut there we call this a new node. Leave a peanut there, it now becomes an old node. Similarly, a path without peanuts or a path in which you are currently on and dropping peanuts for the first time is a new path. A path with peanuts already on it and on which you are now dropping crisps is called an old path. Here is now how to solve any maze.
- Start at the entrance and take any path.
- If at any point you come to a new node then take any new path.
- If you come to an old node, or the end of a blind alley, and you are on a new path then turn back along this path.
- If you come to an old node and you are on an old path then take a new path (if such exists) or an old path otherwise.
- Never go down a path more than twice.
If you follow this procedure then you will eventually reach the centre and then get back out again. This of course only happens if no one eats the peanuts, and here we have to hope for the best! Try it out on the examples in the exercises, for which a pencil mark will substitute for the peanuts. For an example, on the network of our maze the method gives as one possible route, the route:
Interestingly enough, if you read the account of Harris' adventures in the Hampton Court maze from the book Three Men in a Boat, you will find that he also used a marker. Instead of a peanut, they used a baby's bun which showed them when they had come back to the same point. Unfortunately as there was only one bun available it didn't help much with solving the maze itself and left the baby hungry. Try this method out and see if you can discover why and how it works.
We have seen how to transform a maze into a network. As we mentioned before, you can think of an underground rail system as a network of connected stations. The internet is a network of computers. In fact, there are many other examples of real systems that we can think of as networks.
The aMazing thing about mathematics is its power to Connect them all!
More information on mazes, networks and many other areas of
mathematics can be found in our forthcoming book,
Mathematics Galore!, Masterclasses, discovery workshops, and team projects in mathematics and its applications by C J Budd and C J Sangwin, to be published soon by OUP.
- Poster Graphic design: AD Burbanks
- Connects concept: HK Moffatt
- Main diagram: AD Burbanks, RE Hunt from idea of HK Moffatt
- Main text: HK Moffatt, RE Hunt, AD Burbanks
- aMazes concept: CJ Budd and CJ Sangwin (Univ. Bath)
- Cretan maze diagram: CJ Budd and CJ Sangwin (Univ. Bath)
- Graph of Permutation Group S4: AD Burbanks from idea of Neil O'Connell
- Maths aMazes text and images Copyright 2000 C J Budd and C J Sangwin, Department of Mathematical Sciences, University of Bath.
- JAVA Applet Copyright 2000, Mr A T Wilson, Dept. Maths, University of Bath.
- Website text: CJ Budd and CJ Sangwin (Maths aMazes), AD Burbanks and RE Hunt.
(By way of thanks to CJ Budd and CJ Sangwin for their contributions to this poster, the faded diagram on the right-hand side of the poster, behind the text, is an abstract of the Bristol/Bath area road network.)
- Radio Controlled? by Robert Leese (Plus, Issue 10).
- Robert Leese explains how the mathematics of colouring graphs (networks) can help avoid interference on your mobile phone.
- Call routing in telephone networks by Richard Gibbens and Stephen Turner (Plus, Issue 2).
- Find out how modern telephone networks use mathematics to make it possible for a person to dial a friend in another country just as easily as if they were in the same street, or to read web pages that are on a computer in another continent.