Networking: Minimal Spanning Tree


Purpose: Learning how to design a network with a minimal total length (known as “Minimal Spanning Tree.”).

Vocabulary: Minimal Spanning Tree & CS Graph
Our society is linked by many networks: telephone networks, utility supply networks, computer networks, and road networks. For a particular network there is usually some choice about where the roads, cables, or radio links can be placed. We need to find ways of efficiently linking objects in a network.
The task of designing a network with a minimal total length is called the Minimal Spanning Tree problem.

Activity #1: Solve the Muddy City Problem (handout)
Journal Entry: Apply the 4 Step Problem Solving Process to Muddy City...then, Execute the Plan.

“Problem Solving Process” – 4 Step  

1. Understand The Problem
   • What is known? 
   • What is not known (This is what I am trying to solve)? 
   • What are the conditions (restrictions or limitations). 
2. Make a plan to solve the problem – This is known as an Algorithm! 
3. Carry out the plan. 
4. Review and Reflect on how the problem was solved.