Activity 9

The Muddy City — Minimal Spanning Trees

Age group: Middle school and up
What you need to know: Basic counting (up to about 50)
Time: About 20–30 minutes
Group size: Works for individuals or a whole class

Focus

• Puzzle solving
• Optimization (finding the best possible solution)
• Planning

Summary

Modern society runs on networks—telephone systems, power grids, computer networks, road systems. For any of these, there's usually more than one way to arrange the connections between points. This activity explores a method for choosing the most efficient set of connections in a network.

Key terms: Minimal spanning trees; greedy algorithms (step-by-step methods that make the best choice at each stage); graph algorithms.

Materials

Each student will need:

• A copy of the map handout (enlarging it onto larger paper makes it easier to work with)
• About 40 counters or small squares of cardboard

The Problem

Imagine a city with no paved roads. After it rains, the streets turn to mud—cars get stuck, and people ruin their boots just walking around. The mayor decides some streets need to be paved, but doesn't want to overspend, since the city also wants to build a swimming pool.

So the mayor sets two rules:

1. Enough streets must be paved so that every house can be reached from every other house using only paved roads (possibly passing through other houses along the way).
2. The paving must cost as little as possible.

The map shows the city's layout, where the number between two houses represents the paving cost for that road. The challenge: figure out the smallest total number of paving stones needed so that everyone can get from any house to any other.

What to Do

1. Hand out the map and explain the muddy city problem using the story above (adjust the details to fit your students' age).

1. Give out the counters. Let students place them on the map to represent paved roads, trying to find the cheapest possible solution. Update the class as better solutions emerge. There are multiple correct answers—different arrangements can all add up to the same lowest total cost.

1. Discuss the strategies students used.

Some students will discover a strong strategy: start with a blank map, and add paved roads one at a time, always choosing the shortest unpaved road available—but skipping any road that would connect two houses that are already connected through other paved roads. This method is guaranteed to produce an optimal (best possible) solution. When there are ties (multiple roads of the same length), choosing a different one first can lead to a different—but equally good—final layout.

Another approach some students may try: start by paving every road, then remove the ones that aren't needed. This can also work, but it takes a lot more effort.

Variations and Extensions

Try the puzzle with a different map layout. City networks can also be drawn in a simpler, more abstract way: houses become circles, muddy roads become lines connecting them, and the number next to each line shows that road's length. Computer scientists and mathematicians call this kind of diagram a graph. (Don't confuse this with the everyday meaning of "graph," like a bar graph showing data—it's a completely different concept.) Note that the line lengths in these diagrams usually aren't drawn to scale.

You might also have students think about how many roads are needed for a city with n houses. It turns out the optimal solution always uses exactly n − 1 connections—that's the minimum number needed to link every house together, and adding even one more connection would just create an unnecessary extra route.

Another extension: have students find real-world networks that could be represented as graphs—like the roads connecting nearby towns, or airline flight routes across a country. Keep in mind that the muddy city method only minimizes total length—it guarantees you can get from any point to any other, but it doesn't consider how convenient the route actually is. Still, many other graph-based methods exist for solving related problems, such as finding the shortest path between two specific points, or the shortest route that visits every point in the network. Turning a real network into an abstract graph is often the first step toward solving these kinds of problems.

What's It All About?

Imagine designing how electricity, gas, or water should reach every house in a new neighborhood. You need a network of wires or pipes connecting all the houses to the utility company. Every house must be connected somewhere in the network, but the specific path the utility takes to reach a house usually doesn't matter much—as long as a connection exists. Designing such a network using the least total material is called the minimal spanning tree problem.

This concept isn't limited to gas and power lines—it applies to computer networks, telephone systems, oil pipelines, and airline routes. (Though, as mentioned, when the network involves moving people, you also need to think about convenience, not just cost.) Minimal spanning trees are also a useful building block for solving other network problems, like the famous "traveling salesperson problem," which asks for the shortest possible route that visits every point in a network.

There are efficient algorithms (step-by-step procedures) for solving minimal spanning tree problems. One simple method that always produces the best solution: start with no connections at all, then add connections one at a time in order from shortest to longest—skipping any connection that would link two points already connected through the network. This is the same strategy mentioned earlier, and it's one that students often discover on their own. It's called Kruskal's algorithm, named after J. B. Kruskal, who published it in 1956.

Further Reading

Harel's Algorithmics discusses minimal spanning trees and explains how they connect to the traveling salesperson problem. Dewdney's The Turing Omnibus includes a section on minimal spanning trees that covers Kruskal's algorithm.