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