Lesson 13: Minimum Spanning Trees
This lesson adapted from Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for copyright restrictions.

Motivation:

We all have experience with several different types of networks: telephone networks, networks of roads, and computer networks for example. One question we might ask about such networks is, "what's the cheapest (or shortest) way to link all the objects together?" This question is explored in the following activity. 

Materials:

  1. Copy of age-appropriate network: Big Muddy City or Little Muddy City (which can be found in CS Unplugged), one per student or pair of students.
  2. Grease pencil, one per student or pair of students. 
  3. Overhead copy of age appropriate network. 
  4. Overhead pen. 

Lesson Plan: 

  1. Do Activity 9: The Muddy City from Computer Science Unplugged.

Conclusion:

In order for a computer to solve a problem like this efficiently, it must be given a precise system for doing so. Computers have no way of figuring out the system for themselves, though they are very good at following the instructions given to them.


Evaluation:

Project: Give each student or pair of students a list of 10 or so (fewer or more depending on level of students) US cities, and tell them that the Transportation Department is thinking of constructing new high speed roadways in place of existing roads. Their goal is to connect all these cities as cheaply as possible.  For younger students, the cost of the project is equal to $1 for every mile of the new roadway.  For more advanced students, the cost of the changing an existing road to a high speed road way is $1 for every mile of interstate, $2 for every mile of state highway, $3 for every county highway, etc. using the road designations on your road atlas.  The students should write up a proposal including at least: 
  1. A picture (graph) representing all the cities with all roads between them labeled with mileages.  (More advanced students should also label the roads with costs.)
  2. A description of the problem in their own words.
  3. A description of the strategy they would employ to find the best solution.
  4. Their solution on the graph and the total cost of the project.

Extensions:

You could have the students try to determine the number of links necessary if there are n houses in the city. It turns out that an optimal solution will always have exactly n-1 links. Have the students explain why this is true. It's true because n-1 links are required to connect all n houses together, and adding one more would create a cycle, which, as mentioned before, could have any edge deleted from it without disconnecting any houses. 

The numbers on the edges can be fractions, decimals, or anything you'd like your students to practice adding.  Also, you can make a new map where the length of the edges indicates the length of the roads, so students have to measure to find the distance.

Standards:

  • NCTM K-4:  1, 2, 3, 4, 7, 8, 10.
  • NCTM 5-8:  1, 2, 3, 4, 7, 13.
  • NCTM 9-12:  1, 2, 3, 4, 12.

Skills:

  • Problem solving / reasoning / communication / connections
  • Strategy development
  • Odd/even number recognition
  • Spatial sense
This lesson adapted from Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for copyright restrictions.