Day 3 Minimum Spanning Tree

 

A spanning tree is one that allows each node to be connected to the rest of the network.  You must use only the arcs that are present, but you do not need to use all of them.  You may lift your pencil at any time.  Have the students find a spanning tree on the top network on example A.  This is like an airline company that does not necessarily have direct flights everywhere, but guarantees that they can get you to each location.  Note: If it is possible to trace a cycle where you return from where you started, then one of the segments is not needed.

 

A minimum spanning tree takes cost (or mileage...) into consideration and wants to make the sum of the numbers as small as possible.  Have students try this by educated guessing on the second network on example A.  Students should come to a consensus that the minimum is 20.  Why might a short piece be worth more?  Possible reasons:  Perhaps it is a part of a road that requires a tunnel to be built.  Maybe it is a piece of pipe that has to go under a lake.

 

Have students try problem 3B by trial and error.  As students begin to discuss smaller and smaller sums, introduce the algorithm below.  Practice with example 3A (2) together and then have the students try it on 3B.

 

Describe an algorithm to find the minimum spanning tree.

  1. Select any node and shade it.
  2. Look at all of the arcs connecting any shaded node to any unshaded node.

2a)                   Choose the arc with the smallest value that is not shaded. 

2b)                   Shade this new node and arc.

  1. Repeat step 2 until all nodes are shaded.
  2. The sum of the shaded costs is the minimum cost of the minimum

spanning tree.

 

An algorithm is simply a set of instructions that allow a solution to be found.  Computer programs are often written using algorithms.

 

 

Day 3 Minimum Spanning Tree WS (A)

3A (1)  Spanning Tree = Airlines

3A (2) Minimum Spanning Tree

 


Day 3 Spanning Tree

Worksheet 3A - Answers

 

3A (1)  This is only one of many possible spanning trees.

3A (2) Minimum Spanning Tree

ANSWER = 20

           

Day 3 Minimum Spanning Tree WS (B)

 

 

Day 3 Minimum Spanning Tree

Worksheet 3B - Answers

Minimum Sum = 311

 

Note – More than one set of connections might be possible; however, the minimum sum should remain the same. 

update.pk ||You are 1125740 visitor