Activity 9

The Muddy City—Finding the Shortest Connections

Age group: Middle elementary and up.

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

Time: About 20 to 30 minutes.

Group size: Works for one student or a whole class.

Focus: Puzzle solving, finding the best solution, and planning.

Summary

Our world is full of networks that connect things together. Think about telephone lines, water pipes, computer connections, and roads. When people build these networks, they usually have choices about where to put the roads, cables, or connections. This activity lets you explore how to make the best choices when connecting things together.

Key words: minimal spanning trees (the shortest way to connect everything), greedy algorithms (step-by-step methods that pick the best option at each step), graph algorithms (methods for solving problems using dots and lines).

What You'll Need

Each student needs:

• A copy of the map (it helps to make it bigger by copying it onto larger paper)
• About 40 counters or small pieces of cardboard

What To Do

Once there was a city with no roads at all. Getting around was hard, especially after it rained, because everything turned to mud. Cars got stuck, and people got their boots dirty.

The mayor decided some streets needed to be paved. But the mayor didn't want to spend too much money, because the city also wanted to build a swimming pool. So the mayor made two rules:

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

The map shows the city's layout. The numbers between houses show how many paving stones it would take to pave that road. The challenge is to figure out the smallest number of paving stones needed so everyone can reach everyone else.

Steps:

1. Give each student a copy of the map. Explain the muddy city problem using the story above (you can change the story a bit depending on the age of your students).

1. Hand out the counters. Let students try to solve the puzzle by placing counters where they think the paved roads should go. As students find better solutions, share this with the class. There are solutions that use only 23 paving stones total—and there's more than one way to reach this same low number!

1. Talk about the strategies students used to solve the puzzle.

Some students will discover a smart strategy: start with an empty map, then add counters one at a time only when needed, until all the houses are connected. This strategy works great! In fact, if you always add the shortest paths first (skipping any path that would connect houses that are already connected), you're guaranteed to find the best possible solution. Different solutions happen when students choose a different order for paths that are the same length.

Another strategy is to start by paving every single road, then remove the roads that aren't needed. This can also work, but it takes a lot more effort.

Try This Too

Students can try solving other "muddy cities." There's a simpler way to draw these problems: use circles for houses, lines for muddy roads, and numbers next to the lines to show each road's length. Computer scientists and mathematicians call this kind of drawing a graph. This might be confusing at first, because in math class "graph" often means a bar graph or chart with numbers. But this is a different kind of graph—just dots and lines showing connections. (Note: the road lengths on these simpler drawings aren't drawn to scale.)

You could also ask students to figure out how many connections are needed if there are a certain number of houses, let's call it "n" houses, in the city. It turns out the best solution always uses exactly one fewer connection than the number of houses (n − 1 connections). That's always enough to link every house together. Adding even one more connection would just create an extra, unnecessary route.

Another idea: have students look for real-life networks that could be drawn as a graph, like the roads connecting nearby cities, or airplane flight routes across a country. However, the muddy city method isn't perfect for these networks. It only makes the total distance as short as possible—it doesn't think about how convenient the route actually is for travelers. Still, there are many other methods for solving graph problems, like finding the shortest path between two points, or finding a route that visits every point. Drawing the network as a graph is a great first step toward solving these kinds of problems.

What's It All About?

Imagine you're designing how electricity, gas, or water reaches a brand-new neighborhood. You'd need a network of wires or pipes connecting every house to the utility company. Every house must connect to the network somewhere, but the exact path the pipes or wires take usually doesn't matter much—as long as a connection exists. Designing a network that uses the least amount of material is called the minimal spanning tree problem.

Minimal spanning trees aren't just useful for gas and power lines. They help solve problems for computer networks, telephone lines, oil pipelines, and airline routes too. But remember: when the network involves people traveling, you also need to think about how convenient the route is, not just how short it is. Minimal spanning trees are also a helpful tool for solving other tricky graph problems, like the "traveling salesperson problem," which looks 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: start with no connections at all, then add connections in order from shortest to longest, but only add a connection if it links two parts of the network that weren't connected before. This is the same strategy mentioned earlier—and many students have figured it out on their own! This method is called Kruskal's algorithm, named after J.B. Kruskal, who published it in 1956.

Further Reading

You can learn more about minimal spanning trees in the book Algorithmics by Harel, which also explains how they connect to the "traveling salesperson" problem. The Turing Omnibus by Dewdney also has a section on minimal spanning trees that explains Kruskal's algorithm.