How does a map app determine the best way to get you from one place to another? Roads aren’t always straight, and they can connect to each other in many different ways. For long trips, there can be thousands of ways to go. How do you know which one is best? Let’s look at a real example of this kind of problem.

The phone lines in this town were blown down by a windstorm. The whole town is disconnected from the Internet. The mayor wants to install new high-speed Internet for everyone. She is asking you for help to design a single network that connects all the buildings to each other. To help the network cost less, it should use as few segments of cable as possible. Map of buildings connected by paths

Try it with someone else

There are a lot of different ways to approach this problem. See how someone else might solve it. It can be a classmate or someone who lives with you. Ask them to explain what they are thinking as they go. What do they do differently than you? What can you learn from each other?

Instructions

Using the map on page 2 of your booklet:

  1. You can start anywhere. Think about which paths between buildings will keep your cost low.
  2. Connect buildings by filling in segments with a pencil or small counters - dry beans work great!
  3. Check to make sure you can trace the path from any building to every other building.
  4. Count the number of spaces you used. That’s your total cost.
  5. Can you find a different way to connect the buildings using fewer segments?
namespaces/google.engedu.csfirst/contents/Activity-66697451272335638413452629842935431532en