Social media sites keep track of their users and how they are connected to each other. Users who are directly connected are termed first degree connections. Second degree connections are users who are not directly connected but they have common first degree connections. They are a "friend of a friend". Social media sites search for second, and possibly third, degree connections and suggest these to a user as people they may know.

4 - Minimum Spanning Trees

Summary

In this lesson, students will examine the nature of spanning trees, be introduced to minimum spanning trees in weighted networks, and determine the mimimum cost solution to pave a muddy city, both using inspection and Prim's algorithm.

Context

Sequence of Lessons

In Lessons Two and Three, students learnt about trees and weighted networks. This lesson will examine spanning trees and minimum spanning trees and how to determine them.

Lesson Five will extend the students' skill set by introducing the finding of shortest path.

Prior Learning

In addition to exposure to algorithms in earlier stages, this lesson will build upon what the students learnt about trees in Lesson Two and weighted networks in Lesson Three.

Future Learning

While shortest paths do not always align with a minimum spanning tree, there is significant overlap. Thus, the skills the students build in this lesson should assist in Lesson Five, as well as being general mathematical knowledge that might come up later in life.

Goals

Distinguish between a tree and a spanning tree and appreciate characteristics of spanning trees including the number of edges making up a spanning tree

Solve optimisation problems through finding minimum spanning tree, both by inspection and Prim's Algorithm

Reason why algorithms are useful

Syllabus Content

Identify and use network terminology: spanning tree, minimum spanning tree, by inspection, Prim's Algorithm (not included in syllabus vocabulary list)
determine the minimum spanning tree of a given network with weighted edges.
- determine the minimum spanning tree by ~~using Kruskal’s or~~ Prim’s algorithms or and by inspection
- determine the definition of a tree and a minimum spanning tree for a given network

use associated techniques to optimise practical problems (from Subtopic Focus)

Working Mathematically

Build fluency and understanding related to spanning trees

Solve optimisation problems through finding minimum spanning trees

Reason why algorithms are beneficial

Possible Misconceptions

There is only one possible minimum spanning tree for a network (no literature reference found)
Spatial positioning of vertices in the network diagram is significant (Rosenstein, 2018)

Vojtěch Jarník

Lesson - Finding Minimum Spanning Trees

In this lesson, the students will be asked to work on their own diagrams and calculations but also encouraged to discuss in groups and assist one another. The advantages to this approach are:

Students will see that there are several different ways to draw trees
Students will be able to check answers against one another
The teacher will be able to examine the output of each student to ensure they are mastering both what has been taught in previous lessons but also what is being taught in this lesson [AFL]

Time
(min)

0 - 10

Teacher

As both a warm up activity and also an exploration of spanning trees, instruct the students to create four network diagrams:

On the first, draw 5 vertices and 3 edges, with no cycles
On the second, draw 5 vertices and 4 edges, with no cycles
On the third, draw 5 vertices and 5 edges
On the fourth, draw 4 vertices and 3 edges

Ask the students whether the first network represents a tree.

Ask the students whether the second network represents a tree and, if so, what's the difference between the first and second tree.

Introduce the term SPANNING TREE [LIT].

Ask the students to examine the third and fourth networks. Ask the students whether they can see any patterns in regards to the number of edges in a spanning tree, guiding them to the conclusion that the number of edges in a spanning tree is one less than the number of vertices in the network.

Students

Students draw the networks as requested.

The students discuss what defines a tree and the difference between the trees in networks 1 and 2 [WM - Fluency]. Students then listen to the meaning of spanning tree.

Students examine the relationship between the number of vertices and number of edges in spanning trees [NUM], eventually coming to the conclusion that the number of edges in a spanning tree is one less than the number of vertices [WM - Reasoning].

10 - 15

Ask students to share the answers to the question posed to them in the homework for Lesson Two, namely what are the pros and cons of trees versus more generic/cyclical networks.

Emphasise the points that systems built based on trees would use the least amount of material but would also have no redundancy.

Students share their answers for the homework of Lesson Two.

Students further discuss the pros and cons of building systems based on trees [WM - Justification].

15 -30

Remind students of the weighted networks [LIT] that the learnt about in the previous lesson.

Introduce the Muddy City problem from the NSW Education Networks Resources website... https://education.nsw.gov.au/teaching-and-learning/curriculum/mathematics/mathematics-curriculum-resources-k-12/Mathematics-11-12-resources/year-12-networks

Have the students create a network that represents all the houses in the city, all the muddy paths in the city, and the length (weight) of each of these muddy paths.

Check on the diagrams the students are making to ensure they have mastered drawing networks in general and specifically weighted networks [AFL].

Students examine the Muddy City problem and create a network representing all the houses and muddy paths in the city.

Then students count the length of each muddy path [NUM] and apply that weighting to the network.

30 - 45

Introduce the concept of Minimum Spanning Tree [LIT] and point out its applicability to the Muddy City problem.

Ask the students to determine a minimum spanning tree for the Muddy City and then compare their answer with those of classmates.

Keep track of the time it takes students to complete this task for later comparison to the Prim's Algorithm approach.

Once the students are done, ask them the following questions:

Was this an easy or hard process?
How certain are the students on having found a minimum spanning tree?

Students learn the meaning of minimum spanning tree and how it applies to the Muddy City problem.

Then students determine minimum spanning trees for this problem by inspection [NUM] [WM-Problem Solving].

Students ponder and respond to the questions about this process.

45 - 55

Introduce Prim's Algorithm [LIT] and review its steps.

Ask the students to use Prim's Algorithm to find a minimum spanning tree for the Muddy City problem and compare that tree to the first one they found. Keep track of the time it takes for the students to find a minimum spanning tree using this algorithm.

Once the students are done, note the difference in times between finding the first minimum spanning tree and the second. It's assumed that finding by inspection would have taken longer.

Also, ask the following questions about this process:

Was it easier or harder than finding the minimum spanning tree by inspection?
What would the difference be for larger networks?
Were the students more confident that they had truly found a minimum spanning tree?
Did the algorithm take less thinking power?

Students learn about Prim's Algorithm and its steps.

Students apply the rules of this algorithm to find a mimum spanning tree for the Muddy City problem [NUM].

Students compare the first minimum spanning tree they found with the one they found through Prim's Algorithm.

Students ponder and respond to the questions about this process [WM - Reasoning].

55 - 60

Mention that there are other algorithms that can be used to find minimum spanning trees and that the subject of the next lesson will be one of these other algorithms.

Students take on board that there is more than one algorithm to determine minimum spanning tree..

Differentiation

There is intentionally little differentiation built into this lesson as it is an opportunity for the teacher to observe how each student is faring individually. That being said, peer assistance and comparison will be encouraged and the teacher should provide additional scaffolding as required, either individually or for the whole class.