Networking: Minimal Spanning Tree & CS Graph


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.

Activity #2: CS Graph (handout)
Apply a CS Graph to the Muddy City layout.

Activity #3: Traveling Salesman (handout)
Solution!

Project: "Student Trip": Each student will create a scenario that will present a Minimal Spanning Tree and a C.S. Graph.
Model: Student Trip Example
Handout: Student Trip

Preparation
Students will reflect and write down 5 destinations they traveled to in the past week – these trips could have been taken on different days. I recommend that the destination be limited to your local area. The student needs to determine what is the shortest path between these locations

Scenario
Write a real or fictitious story explaining your need to go to these destinations. The trip must always begin at your home and finish at your home.

Minimal Spanning Tree
“Most Direct!”: Each student will create a Minimal Spanning Tree on a Map. Show the order from 1st to last and the distances.  Remember, the goal of a Minimal Spanning Tree is to find the shortest route within whatever constraints are provided. (Refer to the teacher’s model)

C. S. Graph
Each student will create a Graph in which the destinations are represented by dots and the lines connecting the dots state the distances and the approximate times to drive the distances. Your home must be part of the Graph (Refer to the teacher’s model).

Your Presentation
Each student will present their diagrams using Google Slides.
Here is a link to a Google Slides online video training guide I created for you: Google Slides Video Tutorial!

Using Maps
Use Google Maps to get distances and times. It is very simple to use. To Access Maps in Google Slides, go to Main Menu/Tools/Research.  Search for a map, drag it into the Slide and edit!

Window Screen Shot:
Either,
Press “PrtSc” ->. An image of the screen is copied to the computer memory. Just open your Google Slide and paste..
Or,
Press the Windows Key and “PrtSc” -> A .png file is created & saved to the Pictures folder.