# Minimal Spanning Trees

### The Muddy City

Networks are everywhere in modern society: roads, wires, water and gas pipes all connect one place to another. Computers are built of networks at many levels, from the microscopic connections between transistors in a chip to the cables and satellites that link the internet around the world. People who build networks often need to work out the most efficient way to make connections, which can be a difficult problem.

This puzzle shows students the decisions involved in linking a network between houses in a muddy city. It can lead on to a discussion of minimal spanning tree algorithms for optimizing networks.

### Related Resources

• An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there’s some extra technical information.
• More lessons and activities:
• nrich Maths has the following activities with notes and solutions provided:
• [Requires registration] Cre8ate Maths UK has a resource called Working for Efficiency that looks at 3 different network problems that are encountered in practical logistical planning. The resource helps in learning how the Prim’s algorithm works in the real world.
Note: You will need to register (free) as a teacher at Cre8ate Maths UK to access this resource
• [Requires registration] TES Connect UK contributor numskull has the Minimum Connector Program. Instructions: Create and solve minimum connector problems interactively using the power of Excel. Use for whole-class work with a projector, or use the practice sheets for individual/small group work at a workstation. The answer is illustrated step-by-step on a matrix, which can also be input by the user if preferred (for the graphical version of the algorithm, simply draw the graph alongside or on a piece of paper). On the practice sheets your answers can also be checked by the program.
Note: Teachers will need to register on TES Connect UK in order to access resources.