• Apply Prim's or Kruskal's algorithm to find the minimum spanning tree of a given network

• Construct a network and measure the distance between vertices to find weight values

Working Mathematically

• Discuss the benefits of tree-structured networks in real-world contexts (Understanding, Fluency)

• Recall the process of determining minimum spanning trees through Prim's algorithm (Fluency)

• Define and compare Kruskal's algorithm with Prim's algorithm (Fluency, Reasoning)

• Apply Prim’s and Kruskal's algorithms to determine the minimum spanning tree of a given network (Fluency, Problem-Solving)

• Calculate the total weight of a spanning tree by summing the weights of the included edges (Fluency)

• Construct network diagrams and gather information about weight values through measurements (Fluency, Communicating)

Introduction

Working Mathematically: Fluency, Reasoning

Sequencing Activity (10 min) [LIT]

Hand each student a worksheet with two sets of images and instructions that detail how to determine the minimum spanning tree.

Check that students, using their knowledge from the last lesson, are able to separate and order the images and instructions related to Prim's Algorithm (AFL).

Go through the worksheet with students and introduce them to the focus of this lesson - Kruskal's Algorithm - which provides students an alternative method to determine the minimum spanning tree. After students correct sequence Kruskal's algorithm, ask them the following question (AFL):

• What are the differences between Prim and Kruskal's algorithms?

• Which algorithm do you prefer?

Body 2

Working Mathematically: Fluency, Problem-Solving

The Muddy City (15 min)

Provide each student with the Muddy City Problem worksheet (and each group an A4-sized copy of the map). Select students to take turns reading the Muddy City Problem. Summarise the following for students:

Roads need to be paved for a city that experiences many rainstorms, to make commute more comfortable and convenient for residents.

Ensure that the students familiarise themselves with what is expected of them for the activity:

• Students need to plan the number of paved roads that should be placed in the city, marking out the roads deemed to be suitable in the worksheet provided.

• The constraint is that students should minimise the number of paving stones (and therefore the cost) for their new road network.

  • • Offer students the option to use counters to mark out the paving stones by placing a small bucket of counters on each table.

• After that has been established, students need to draw out the network system in a fashion that is more simplistic, akin to what they are used to seeing in the past lessons, and map out the routes they've chosen to use.

After students have redrawn their network diagrams, it should be evident that they have drawn a minimum spanning tree connecting the buildings together. Ask each group to shout out how many paving stones their new road network uses (and write their results on the board) (AFL). Poll which groups used Prim's Algorithm, and which used Kruskal's Algorithm. Ask one group each to re-explain the process (AFL), then ask the class the following question (AFL):

• What is the benefit of creating a spanning tree for this scenario?

Body 3

Working Mathematically: Fluency, Communicating

Sprouts Game (5 min)

For the remainder of the lesson (until the Conclusion), students, in pairs, will engage in a game of Sprouts to construct a network. Following the construction of the network, students will use string and a ruler to find the measurements of the lines involved in the game.

Students should then redraw the network in a new diagram, with the weighted edges labelled. Once completed, instruct students to draw out the minimum spanning tree of their diagram. Check students' diagrams before the end of the lesson (AFL).

Instructions for Sprouts:

1. Draw three spots anywhere on the paper.

2. Each player, in turn, draws a line joining one spot to another spot (or itself) and places a new spot somewhere on this line.

3. No lines may cross, no spot may have more than three lines coming out of it (i.e. we would say that the degree of any vertex cannot exceed three).

4. The game continues until no further moves are possible and the player to make the final move is the winner.

Conclusion - 5 min

Working Mathematically: Fluency, Understanding

Three W's recap (5 min)

With the students in their table groups of four, pose the following questions (AFL):

• • 1. 1. What did we learn today?

       2. What is the relevancy, importance and usefulness of what we learnt today?

       3. What could we do this new knowledge?

Each table group needs to address and answer at least one of the questions. After a few minutes, call on groups to share their responses (AFL). If there is time, get students to elaborate on their responses to ensure that the class has a holistic understanding of the lesson.