This activity from the Nuffield Foundation shows students how to use Kruskal’s and Prim’s algorithms to solve minimum connector problems.
A cable TV company wants to lay cables to connect the towns, laying the cable along the roads shown on a map of the Isle of Wight. They want to connect all of these towns to their cable network using the minimum total length of cable.
The students are then set a second problem involving a theme park, where the manager of the theme park wants to widen and re-surface some of the paths to provide better access to the rides for wheelchairs. His aim is to provide better paths to connect all parts of the theme park, but using the minimum total length possible.
HEALTH and SAFETY
Any use of a resource that includes a practical activity must include a risk assessment. Please note that collections may contain ARCHIVE resources, which were developed at a much earlier date. Since that time there have been significant changes in the rules and guidance affecting laboratory practical work. Further information is provided in our Health and Safety guidance.