- View more resources from this publisherComputer Science Unplugged
The Poor Cartographer - Graph Colouring
Many optimization problems involve situations where certain events cannot occur at the same time, or where certain members of a set of objects cannot be adjacent. For example, anyone who has tried to time-table classes or meetings will have encountered the problem of satisfying the constraints on all the people involved. Many of these difficulties are crystallized in the map colouring problem, in which colours must be chosen for countries on a map in a way that makes bordering countries different colours. This activity focuses on this problem. The resource begins with an explanation of the task followed by the activity itself requiring students to colour a map with no two adjacent sections of the map being the same colour. There are a number of variations of the task and further explanation of the four colour theorem. The resource concludes with a number of examples of maps for use in the classroom. This collection of twenty activities from Computer Science Unplugged is designed to aid the teaching and learning of computer science through engaging games and puzzles using cards, string, crayons and lots of running around.
Show health and safety information
Please be aware that resources have been published on the website in the form that they were originally supplied. This means that procedures reflect general practice and standards applicable at the time resources were produced and cannot be assumed to be acceptable today. Website users are fully responsible for ensuring that any activity, including practical work, which they carry out is in accordance with current regulations related to health and safety and that an appropriate risk assessment has been carried out.
Downloads
-
Graph colouring 153.55 KB