A Rubik's cube can be represented by a network where a vertex represents one of the possible positions of the cube and an edge represents the rotational move which changes the cube from one position to another. The diagram above only shows the positions for a full rotation of the right side of the cube. Even though a 2x2 cube has more than 3.6 million possible positions, some computer programs can still find a solution in less than a second. A 3x3 cube has more than 43 quintillion possible positions, making the search problem much more complex than the 2x2 cube.

5 - Kruskal's Algorithm

Summary

Lesson 4 covered minimum spanning trees (MSTs) and finding MSTs via inspection and Prim's algorithm. In this lesson, students learn another algorithm, Kruskal's algorithm, to determine a MST. The lesson will build towards Kruskal's algorithm by providing a network diagram where the students are required to connect the vertices using edges in the form of paddle pop sticks. The students make choices regarding which paddle pop sticks to use and which to discard, leading to strategies that mirror or are close to Kruskal's algorithm. A formal description of the algorithm is presented. Comparisons between Prim's and Kruskal's algorithms are explored in terms of their steps and how the MST progresses.

Outcomes

Lesson Goals

Students can describe Kruskal's algorithm and apply it to find a minimum spanning tree.

Content

Syllabus Content Indicators

Students determine the minimum spanning tree by using Kruskal's algorithm.

Lesson

Materials/Resources

Network 1 diagram (solution)

Network 2 diagram (solution)

Paddle pop sticks with edge weights written on them

Lesson Plan

Time
(min)

0 - 5

Teacher

Teacher explains and models the activity:

A new light rail network is being planned. The stops are shown in the map as vertices

and the edges are possible routes for the tracks. The rail network is to be built with

minimal cost but every stop must be connected to the network somehow. The cost of each track is shown as the edge weight on the map.

The paddle pop sticks represent the tracks and have the cost written on them. Working

in pairs, take turns to choose a track to build until all stops are connected to the network. At each step, note down which track is chosen (identified by the 2 vertices it connects) and the cost of the track. The chosen track should be placed on the network diagram to show that it is used and that the vertices are connected.

Students

Students listen to instructions for the activity

5 - 10

Teacher provides first network diagram and paddle pop sticks.

10 - 20

Circulate around the room to observe students working on the problem. Assist students where required.

Students work on the problem.

20 - 25

Ask students the cost of their spanning tree.

If some students have a spanning that is not minimal, ask them to consider if there is a track that they could have chosen differently.

Ask a student pair to explain their process for choosing each track.

Students answer with their spanning tree cost.

Students describe how they chose each track.

25 - 35

Teacher provides the second network diagram and paddle pop sticks.

Students work on second problem.

35 - 40

Ask if students used the same procedure? Did they have to modify or refine any of their steps or rules?

Students discuss their procedure for the second network diagram.

The second network diagram is different to the first one in that the solution starts out as two separate branches. At some step in the procedure, an edge must be selected to join vertices which are on the separate branches. How does this fit with the students' prior criteria for choosing edges? This presents an opportunity to discuss and refine the procedure so that it is generalised.

40 - 55

Present Kruskal's algorithm using the two network diagrams as examples.

Discuss how Prim's and Kruskal's algorithms differ:

Prim's starts with an arbitrary vertex selection
Kruskal's starts with selection of edge with lowest cost
Prim's algorithm always has a connected tree
Kruskal's algorithm may at times have separate branches

Students follow the explanation and contribute to discussion