Activity 9

The Muddy City — Shortest Connecting Roads

Who this is for: Kids in the middle of elementary school and up.

What you need to know first: How to count to about 50.

Time: About 20 to 30 minutes.

Group size: You can do this alone or with a whole class.

What you'll practice:

• Solving puzzles
• Making the best choice (called "optimizing")
• Planning ahead

What's This About?

Our world is full of networks. A network is a bunch of things connected together, like telephone lines, water pipes, computer connections, and roads. When people build a network, they often have choices about where to put the roads or cables. This activity lets you try out one smart way to pick the best connections.

Big words you'll learn: minimal spanning tree (the shortest way to connect everything), greedy algorithm (a simple step-by-step plan for solving a problem), and graph (a picture showing how things connect).

What You Need

Each person needs:

• A copy of the map on page 96 (it works best if you make it bigger, like double-size)
• About 40 counters or small squares of cardboard

The Story

Once there was a city with no paved roads. When it rained, the ground turned to mud. Cars got stuck. People got mud on their boots!

The mayor decided some streets needed to be paved. But paving costs money, and the city also wanted to build a swimming pool. So the mayor made two rules:

1. Every house must be able to reach every other house using paved roads (you can pass through other houses along the way).
2. The paving should cost as little as possible.

The map on page 96 shows the city. Numbers between houses show how many paving stones it would take to pave that road. Your job: figure out the fewest paving stones needed so everyone can reach everyone else.

What To Do

1. Give each person a copy of the map. Explain the muddy city story (you can change the story a bit to fit your class).

1. Hand out the counters. Let everyone try to solve the problem by placing counters where they think roads should be paved. Talk about it as a class when someone finds a better answer. There can be more than one correct answer! Two different answers might both use the same total number of stones — like 23 stones, for example.

1. Talk about how everyone solved the puzzle.

Some kids might start with an empty map and add counters only when needed to connect houses. This is a great strategy! If you always add the shortest road first — but skip any road that would connect two houses that are already connected — you will always find the best answer. Trying different orders for roads of the same length gives different (but equally good) answers.

Other kids might start by paving everything, then removing roads that aren't needed. This can also work, but it takes a lot more effort.

Try It a Different Way

You can try other "cities" too! Instead of drawing houses and streets, you can draw circles for houses and lines for roads, with a number next to each line showing its length. This is called a graph. Scientists and mathematicians use graphs to show how things connect. (Note: this kind of graph is different from a bar graph that shows number data — same word, different meaning!)

Here's something to think about: if a city has a certain number of houses, how many roads do you need? It turns out you always need exactly one less road than the number of houses. That's enough to connect everyone — and adding even one more road would just be extra, since it wouldn't help anyone get anywhere new.

You could also look for real-life networks that work like this — like roads between nearby towns, or airplane flight routes. But be careful: this muddy city method only finds the shortest total distance. It makes sure you can get anywhere, but it doesn't always find the most convenient route. Still, turning a network into a graph is a great first step toward solving lots of problems like this.

Why Does This Matter?

Imagine you're planning how to bring electricity, gas, or water to a brand new neighborhood. You'd need wires or pipes connecting every house to the power or water company. Every house needs to connect somehow — but the exact path usually doesn't matter, as long as a path exists. Finding the shortest total network like this is called the minimal spanning tree problem.

This idea isn't just for gas and water pipes. It also helps with computer networks, telephone lines, oil pipelines, and airplane routes. (Remember, though — when people are traveling, convenience matters too, not just cost!) This method is also a helpful first step for solving other tricky puzzles, like finding the shortest route that visits every single point in a network (sometimes called the "traveling salesperson problem").

There are smart step-by-step methods (called algorithms) for solving these problems quickly. One simple method: start with no roads at all. Add roads one at a time, starting with the shortest one. But skip any road that connects two houses that are already connected. This method works so well that some kids figure it out on their own! It's called Kruskal's algorithm, named after J.B. Kruskal, who published it in 1956.

Want to Read More?

• Algorithmics by Harel talks about minimal spanning trees and the traveling salesperson problem.
• The Turing Omnibus by Dewdney has a section on minimal spanning trees and Kruskal's algorithm.