D1: Route Inspection
Imagine that you are a road cleaner. You have a network of roads to clean and you must return back to base at the end of the day. What is the best route to take? In this instance the best route is the shortest and the weights on the arcs represent the lengths of the roads.
If you can start at a vertex and travel along each road without taking your pen off the paper or retracing your steps, then obviously that is the fastest route. But this is not always possible.
The map above shows part of the German/Prussian town of Konisgsberg. The town has a strange river flowing through it and there are bridges across the river (a to g on the map). The question is: can you start somewhere and cross every bridge exactly once? Have a go to see if you can do it.
To make this map into a graph, use a node to represent each of the four seperate bits of land, A, B, C and D. Use arcs to connect the land (ie the arcs represent bridges). There are two bridges that join C to A so we need two arcs.
Now see whether you can draw this without lifting your pen or retracing your steps. Have another go. And another. Are you convinced that it is impossible? Can you prove it?
The Chinese Postman Problem
The Route Inspection Problem is often called the Chinese Postman Problem. Instead of cleaning the streets, imagine that you are a postman delivering mail to all the houses in the streets
By the way, the problem is called the Chinese Postman Problem because it was invented by a Chinese mathematician in the 1960s; it is nothing to do with the postman being Chinese.
As mentioned above, if the graph can be drawn without retracing or lifting your pen it is easy to find the minimum length route. Such graphs are called Eulerian, after the great Swiss mathematician Leonhard Euler. But these graphs are trivial - the ones you will meet at A Level aren't so easy.
Let's have a go a solving one of these problems. Starting and finishing at A can you find a route through the network such that you don't retrace your steps?
Now try to see why this graph is not Eulerian. Count the number of lines coming out of each of the nodes. For A this is two, for B it's three and so on. This number is called the valency of the vertex. I'll explain what I'm on about in the following clip...
The Handshake Theorem
As I try to explain in the video clip, the Handshake Theorem says that because each line adds 2 to the total valency, the total must always be even. This means that there can't be just one odd vertex (else the total would be odd). In fact the number of odd vertices must be 0, 2, 4,... - an even number!
If There Are 2 Odd Vertices
A network with all even vertices is very easy to solve the Chinese Postman Problem for. If there are two odd vertices we must add extra arcs (ie go down roads more than once) to make the odd vertices even. There are always amany ways of doing this, we just need the shortest. In the example above, B and D are odd so we need to find the shortest route from B to D. In this case it's easy to find because there aren't many that we need to consider. The direct route is the shortest.
If we repeat the BD route then it is very easy to find a route for our postman. In fact it's almost impossible not to.
So, if there are 2 odd vertices we join them up in the shortest way to make them even - the rest is easy.
What About 4 Odds?
If there are four odds then we need to make them even by repeating routes. To do this we pair them up. Lets say that the four odds are W, X, Y and Z. Wee need to find some way of joining them up to make them even. Fortunately it's quite easy.
We pair them up. Join W to X and join Y to Z, then they're all even. But maybe joining W to Y and X to Z is better. Maybe joining W to Z and X to Y is better. If we try all 3 possible pairings and choose the smallest then we are guaranteed the best route. Again I'll explain this in a clip.