Minimal Spanning Trees
Networks are everywhere in modern society: roads, wires, water and gas pipes all connect one place to another. Computers are built of networks at many levels, from the microscopic connections between transistors in a chip to the cables and satellites that link the internet around the world. People who build networks often need to work out the most efficient way to make connections, which can be a difficult problem.
This puzzle shows students the decisions involved in linking a network between houses in a muddy city. It can lead on to a discussion of minimal spanning tree algorithms for optimizing networks.
-
Blaine Booher from the University of Cincinnati has a variation on the Minimal Spanning Trees activity called Internet Routing where students learn a brief overview of the history of the internet and its impact on society. Students work to understand internet routing and how all of the computers on the internet are interconnected by using the analogy of roads in a town. This activity was developed for high school students.
-
An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there's some extra technical information.
-
The Mathmaniacs web site has a similar activity (lesson 13)