Route Planning in Windsor

First some history

It is said that in Konigsberg, Germany, 1735, there was a river that ran through the city that split into two streams and then joined together again to form an island. There were seven bridges crossing the river at various places. The townsfolk of Konigsberg wondered whether or not they could take a walk around the city crossing each bridge exactly once.

They could never find a way, and they could not work out why not.

The answer to this problem started a whole new branch of mathematics called Graph Theory. The solution was proposed by Leonard Euler, born in 1707 in Switzerland, and one of the most gifted of all mathematicians.

Leonard Euler approached this problem by labelling different places in the city with letters; these are called vertices. He represented the bridges as lines and these are called arcs. The completed picture is called a graph.

All four of the vertices in the Konigsberg graph have an odd number of arcs connected to them. This is really important; take one of these vertices, A, with three arcs connected to it. Imagine you are walking along, the first time you get to this vertex, you can leave by another arc. But the next time you arrive, you cannot, as you have used all three arcs once each already. So you would then be stuck there unless you used an arc that has already been used.

The number of arcs attached to a vertex is said to be its valency. So every vertex with an odd valency has to be either the start or the end of your journey. The rest of the vertices must have an even valency.

If you wish to start and end a city walk in the same place without having retraced your steps once then you must plan a route in which every vertex (any point where two or more routes meet) has an even number of arcs joining it. In this way it may be possible to complete a journey around a graph starting and finishing in the same place without repeating an arc. If so, the graph is said to be fully traversable. If exactly two vertices are left with an odd number of arcs then it may be possible to start at one of these points and finish at the other.

There are two possible ways to make all the valencies of the vertices even:

1. Decide to abandon one or more routes.

2. Decide on one or more routes that may be repeated. Repeated routes are represented by two arcs.

Planning a Walk In Windsor

Applying a few simple graph theory principles to a proposed tour of a town or city can make all the difference.

Here is a route planning problem based in Windsor. The aim is to devise a traversable route starting and finishing at the Central Train Station, taking in all the best routes and sights.

Here is a hand drawn version of the Windsor Town Centre map with interesting walking routes (that take in the Castle, Guildhall, Parish Church, Theatre, Eton Bridge, The Thames, Tourist Information, shops, restaurants and cafes) marked on. It also has labelled vertices where these paths meet.

This map has been made into a graph; vertices are labelled and have their valencies in brackets.

There are four odd valency vertices: A, N, H, and T.

To make all the vertices even it is proposed that routes AN and HX are abandoned and TX (one of the shortest arcs) is repeated. Notice that TX is now represented by two arcs.

A possible journey then becomes SISABNHITXCWGLWXTPKS – a perfect visitor’s walk around Windsor! Walking at a steady and relaxed walking pace, this is a not a long walk, but add in a coffee stop, some shopping, lunch, a castle visit, a scenic bus tour, a boat trip and an evening trip to the theatre and day is more than complete.

Maybe it’s time to go back to the graph and turn it into two separate routes – day 1 and day 2! Or maybe it is time to flex some new found maths muscle to plan your own visit to a town or city.