Graph Colouring
Coloring a map (which is equivalent to a graph) sounds like a simple task, but in computer science this problem epitomizes a major area of research looking for solutions to problems that are easy to make up, but seem to require an intractable amount of time to solve.
This activity introduces graph colouring, and leads on to many variations and extensions that reach the cutting edge of computer science.
-
Computing Science Inside Workshop has an activity Graph Colouring which is a nice extension activity to this topic. This workshop aims to introduce pupils to the fundamental Computing Science notion of abstraction: the skill of drawing out the essence of a problem, solving it and then seeing what other problems can be solved using the same techniques. It introduces what seems to be a simple colouring problem for pupils to solve. Pupils will then try to draw out the rules and methods they used to solve the problem and apply them to a different and more realistic instance of the problem. The workshop will consider the importance of abstraction and automating reasoning to aid problem solving in Computing Science.
Note: You will need to apply and register in order to recieve the Workshop Pack for this activity.
-
The Mathmaniacs website has a similar activity (lesson 15).