The Muddy City: Minimal Spanning Trees

Adapted with AI from the original open resource by CS Unplugged. Nothing is invented — only the reading level changes.

Activity 9: The Muddy City — Minimal Spanning Trees

Age group: Middle elementary and up.
Abilities assumed: Being able to count to about 50.
Time: About 20 to 30 minutes.
Size of group: From individuals to the whole classroom.

Focus:

Puzzle solving.
Optimization (finding the best possible solution, not just any solution).
Planning.

Summary

Our society is connected by many kinds of networks: telephone networks, water and electricity networks, computer networks, and road networks. For any of these networks, there is usually a choice about where the roads, cables, or connections should go. This activity explores one way to figure out the smartest way to connect things in a network.

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

Materials

Each student will need:

A copy of the map handout (it works best if enlarged onto bigger paper).
Counters or small squares of cardboard (about 40 per student).

What to Do

Once upon a time, there was a city with no roads. Getting around was especially hard after it rained, because the ground turned to mud — cars got stuck, and people got their boots dirty. The mayor decided some streets needed to be paved, but didn't want to spend more money than necessary, since the city also wanted to build a swimming pool. So the mayor set two rules:

Enough streets must be paved so that everyone can travel from their house to anyone else's house using only paved roads (they can pass through other houses along the way).
The paving must cost as little as possible.

The map handout shows the layout of the city. The number of paving stones marked between each pair of houses shows the cost of paving that road. The challenge is to figure out the smallest number of paving stones needed so that people can travel from any house to any other house.

Hand out a copy of the map to each student and explain the muddy city problem using the story above. (Feel free to adjust the story to fit the age of your students.)

Give out the counters and let students try to find efficient solutions by placing counters on the roads they think should be paved. Update the class as students discover better solutions. There are two equally good solutions shown in the figures, both costing just 23 paving stones. As this shows, a problem like this can have more than one correct answer — as long as each answer has the same total cost.

Discuss the strategies students used to solve the problem.

Some students will discover the strategy of starting with a blank map and gradually adding counters only when needed, until all the houses are connected. This is a smart strategy — in fact, it's guaranteed to give the best possible solution if you add roads in order from shortest to longest, but only add a road if it connects two parts of the city that weren't already linked. Different solutions come from changing the order in which same-length roads are added.

Another strategy some students might try is starting with every road paved, then removing the roads that aren't needed. This can also lead to a correct solution, but it takes a lot more work.

Variations and Extensions

Students can try solving other "muddy cities." One example shows a more abstract, simplified version of a city that's quicker to draw and easier to work with: houses are shown as circles, muddy roads as lines, and the length of each road is written as a number next to the line. Computer scientists and mathematicians often use this kind of simplified diagram to show relationships between objects — they call it a graph. This can be confusing at first, since "graph" usually means a chart of numerical data, like a bar graph. But the graphs used in computer science are a different idea entirely, unrelated to bar charts. (Note that the road lengths in these diagrams aren't drawn to scale — the numbers matter, not the actual line lengths.)

You could also have students think about how many roads are needed if a city has n houses. It turns out that the best solution will always use exactly n − 1 connections. That's enough to link every house to every other house — adding even one more connection would just create an unnecessary extra route.

Another extension is to have students look for real-life networks that could be shown as a graph, such as the roads connecting nearby towns, or airline flight routes across a country. However, the muddy city method may not work perfectly for these real networks, because it only minimizes the total length of the roads or flights. It guarantees you can get between any two points, but it doesn't consider how convenient or direct the route actually is. Still, there are many other algorithms that can be used on graphs — for example, finding the shortest path between two specific points, or the shortest route that visits every point. Turning a real network into an abstract graph is often the first useful step toward solving these kinds of problems.

What's It All About?

Imagine you're designing how electricity, gas, or water should be delivered to a brand-new neighborhood. You'd need a network of wires or pipes connecting every house to the utility company. Every house must be connected somewhere in the network, but the exact path the utility takes to reach each house usually doesn't matter much — as long as a path exists. Designing a network like this with the smallest possible total length is called the minimal spanning tree problem.

Minimal spanning trees are useful for much more than just gas and power networks — they help solve problems in computer networks, telephone networks, oil pipelines, and airline routes. But as mentioned earlier, when the network involves moving people around, you also need to think about convenience, not just cost. Minimal spanning trees are also a useful building block for solving other graph problems, such as the famous "traveling salesperson problem," which asks for the shortest route that visits every point in a network.

There are efficient methods, called algorithms, for solving minimal spanning tree problems. One simple method that always gives the best possible answer is to start with no connections at all, then add connections in order from shortest to longest — but only add a connection if it links a part of the network that wasn't already connected. This is the same idea mentioned earlier, and we've seen children discover it on their own! It's called Kruskal's algorithm, named after J.B. Kruskal, who published it in 1956.