Tourist Town - Dominating Sets

Many real-life situations can be modelled in the form of a network or “graph” of the kind used for colouring in the Poor Cartographer – Graph Colouring resource. Networks present many opportunities for the development of algorithms that are practically useful. In this activity, the junctions, or “nodes,” are marked in such a way that all other nodes are at most one step away from one of the marked ones. The question is, what is the least number of marked nodes needed? This turns out to be a surprisingly difficult problem.

The resource begins with an introduction and discussion of the concepts contained in the activity followed by the activity, 'ice cream vans'. The solution to the problem is followed by a number of variations and extensions to the task. The resource concludes with further information about networks and graphs.

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.