Colouring graphs and maps may seem an unlikely activity in computer science but it turns out to be a very serious subject and central to the solution of a wide range of related problems - though as we shall see, no solution has yet been found to these.
The idea is very basic. You are given a map with some outlines on it representing borders such as countries or counties. You are either very poor and so have no more than four colours or else you have heard about the Four Colour Theorem and want to check it for yourself. Using no more than four colours your task is to shade the areas so that no two adjacent areas share the same colour.
Work first on map 1. See if you can shade the map with 2 colours. (Note that two countries that meet at a point are taken to be non-adjacent.) To save copies you could mark the areas with coloured counters before shading them (or shade a small area very lightly).
Now try the other three maps. If you finish early see if you can devise a map that requires five colours.
A similar problem might be to make a map of pupils in a room and assign each one a piece of fresh fruit (avoiding the use of dentally compromising sweets!) so that no adjacent pupils get the same type of fruit. How many types of fruit would you need? Draw a plan and name the colours.
The suggestion that a map might need no more than four colours to shade the areas was first proposed in 1852 but not proved until 1976 (The four colour theorem was the first theorem to be proved by computer and some mathematicians will not accept it for this reason.)
Map colouring belongs to a general class of problems called 'graph colouring'. A map of countries can be represented as a graph with countries as nodes and adjacent borders as edges. Likewise, a map of pupils in a room can be represented as a graph rather than a map. Where countries or pupils are adjacent a connecting line is drawn between them.
Practical: Give a name to each area in map 1 and convert it to a graph with nodes and edges with lines drawn between countries that are adjacent on the map. Nodes that are connected may not have the same colour. How does the graph compare with the map? Can you colour the nodes with the same number of colours that you used for the map?
Unlike a map, which requires only four colours, there is no limit to the number of colours that a graph may require. The problem with a graph is to find the minimum number of colours required to solve a given problem.
One problem that can be represented by a graph is the timetable in a school. Subjects are put into nodes and edges are drawn between them when there is at least one pupil who takes both, so they cannot occupy the same set of timetable periods.
Practical: write down these subjects as nodes: Maths, English, History, French. Draw a link between those subjects that are taken by more than one person in the class. What conclusion do you reach about the timetable for these subjects? Now add Spanish and German as additional subjects that can only be studied as alternatives. Draw the links between the nodes and use different colours for nodes that are connected by edges (taken by two or more pupils). What conclusion do you reach about the timetable for these subjects?
Another problem that can be represented by a graph is the transport links between cities. Each city is a node and an edge is drawn when there is a direct link between them. Other problems that can be represented as graphs (there are thousands) include connections between components on a printed circuit board and connections between related tasks in a large project.
These problems are very difficult to solve because it takes a long time to find every combination until the optimum solution is found. In most cases a sub-optimal solution is used, for instance a timetable, which has to be put together in a few weeks and as long as it works it doesn't matter if it is the best possible solution.
Take the map colouring problem. We know that four colours at most are required so for any map the number of combinations is 4n. A map with two areas thus generates 42 combinations or 16 in total (write them out to prove it; 4 of the combinations do not meet the rules). With three countries there are 43 combinations (64), four countries give 44 (256) and so on. For a continent such as Africa the number of combinations is very big and very difficult to complete by hand. What are the possible combinations of colours for the maps that you drew earlier?
The rate of increase in the scale of graph colouring problems is called exponential. In the map-colouring problem the problem grows by a factor of 4 with the addition of each country.
Practical: Find an outline map of Africa with national boundaries and colour it with no more than 4 colours.