Name Date Period

← CS Unplugged

CS Unplugged activity

The Muddy City

About 30 minutesSoloPencil

Once upon a time there was a city that had no roads. Getting around the city was particularly difficult after rainstorms because the ground became very muddy—cars got stuck in the mud and people got their boots dirty. The mayor of the city decided that some of the streets must be paved, but didn’t want to spend more money than necessary because the city also wanted to build a swimming pool. The mayor therefore specified two conditions:

1. Enough streets must be paved so that it is possible for everyone to travel from their house to anyone else’s house only along paved roads, and
2. The paving should cost as little as possible.

Here is the layout of the city. The number of paving stones between each house represents the cost of paving that route. Find the best route that connects all the houses, but uses as few paving stones as possible. Shade the stones you would pave with your pencil (lightly at first, so you can change your mind).

The Muddy City

Total paving stones I used:

What strategies did you use to solve the problem?

Variations and extensions

Here is another way of representing the cities and roads:

The same kind of problem drawn as a graph

The houses are represented by circles, the muddy roads by lines, and the length of a road is given by the number beside the line.

Computer scientists and mathematicians often use this sort of diagram to represent these problems. They call it a graph. This may be confusing at first because “graph” is sometimes used in statistics to mean a chart displaying numerical data, such as a bar graph, but the graphs that computer scientists use are not related to these. The lengths do not have to be drawn to scale.

Find the cheapest set of roads for this graph too. Total:

Now try this method on the graph: start with no roads paved. Pave the cheapest road first, then the next cheapest, and so on, but skip any road that joins two houses that can already reach each other on paved roads. Did you get the same total as before?

Is there more than one best answer for the graph? How do you know?

Can you find out a rule to describe how many roads or connections are needed for a best solution? Does it depend on how many houses there are in the city?

A mail carrier has to walk to every house exactly once and end up back where they started. Could they always do that using only the roads you paved? Why or why not?

What’s it all about?

Suppose you are designing how a utility such as electricity, gas, or water should be delivered to a new community. A network of wires or pipes is needed to connect all the houses to the utility company. Every house needs to be connected into the network at some point, but the route taken by the utility to get to the house doesn’t really matter, just so long as a route exists. The task of designing a network with a minimal total length is called the minimal spanning tree problem.

Minimal spanning trees aren’t only useful in gas and power networks; they also help us solve problems in computer networks, telephone networks, oil pipelines, and airline routes.

There are efficient algorithms (methods) for solving minimal spanning tree problems. A simple method that gives an optimal solution is to start with no connections, and add them in increasing order of size, only adding connections that join up part of the network that wasn’t previously connected. This is called Kruskal’s algorithm after J.B. Kruskal, who published it in 1956.

For many problems on graphs, including the “travelling salesperson problem”, computer scientists are yet to find fast enough methods that find the best possible solution.

Learn more: minimum spanning trees, the traveling salesperson problem, and P versus NP.

Answer key

The Muddy City. Two possible best solutions (paved stones shown black):

The graph. The fewest paving stones is 25. One way: pave every road of length 2, then add roads of length 3 and then 4 only when they join houses that aren’t already connected.

The method. Yes, it gives 25 again: this method (Kruskal’s algorithm) always finds a best answer.

More than one best answer? Yes. In the graph, the two houses along the bottom right can join the rest by either of two different roads of length 4, and both choices give the same total. (The city picture also has more than one, as the two solutions above show.)

The rule. A city with n houses always needs exactly n − 1 roads in a best solution: fewer can’t connect every house, and one more would make a loop that isn’t needed.

The mail carrier. No. A best paving never contains a loop, so there is no way to get back home without walking some roads twice. The mail carrier’s question is a different problem: the traveling salesperson problem.