Resources

• • A4-size-printed Tree Network Examples (see Orientation)

  • Card Sorting Activity (one set per group of 4; see Introduction)

  • Whiteboard (including portable whiteboards), Whiteboard Markers & Erasers

  • Map Images, Projector/Screen (see Body 1)

  • Butchers Paper, Paddle-Pop Sticks, Markers, Rulers, Sticky Tape (see Body 2)

  • Index Cards (see Exit Task)

  • Prepare Slime Mould experiment before next lesson (consult school's lab assistant; buy mould from a science supplier)

Orientation

Working Mathematically: Understanding, Communicating

Floorstorm (5 min) [LIT]

Before the start of the lesson, print out the Floorstorm Photos onto A4-size paper. Place a photo on each group of tables. Before students enter the classroom, instruct them to form their usual group (of four) and select a table to stand by.

When ready, instruct students to use their pens to write down on the paper everything that comes to mind when looking at the photo. Make sure students know to leave space for other groups.

After 30 seconds, rotate groups clockwise and instruct students to brainstorm using their new photo. Repeat this until students return to their original photo.

As a class, discuss the following question(s) for three minutes (AFL):

"What did these examples all have in common?"
"What words did we see keep using or seeing?"

After students recognise the collection of photos as examples of trees, ask them to flip over the paper on their table and to individually each write a (general) definition of what a tree is. Have someone from each group quickly summarise their group's response (AFL).

Introduction

Working Mathematically: Fluency, Understanding, Communicating, Reasoning

Card Sorting Activity, Venn Diagram & Discussion (20 min) [LIT]

Explicitly introduce the new networks vocabulary for students (to add to their Trip Log) (AOL):

• Trees - an undirected network in which any two vertices are connected by exactly one path.

Provide each group with the Card Sorting Activity Set, a whiteboard and whiteboard markers. Instruct students, in their groups, to sort the cards with network diagrams into two categories: tree and non-tree networks.

• For the graphs that are not tree networks, students must write down the reason why (e.g. this graph contains a cycle with four vertices).

• Furthermore, students must then suggest different ways to turn the non-tree graphs into a tree (e.g. remove an edge from this cycle).

Once the class has finished with the activity, get students to summarise their findings by constructing a Venn diagram (with Tree and Non-Tree sets) (AFL). Features that students should note trees cannot have include: cycles, multiple edges, loops. Advise students to add this observation to their Trip Log (AOL).

Discuss the following questions (AFL):

• Why are two vertices in a tree connected by exactly one path?

• How many edges are there in trees? Why?

As a class, discuss how students converted the non-tree graphs into tree networks (likely: remove edges from the graph until it is a tree diagram) (AFL). Draw a connected network diagram on the main whiteboard and invite a student to remove edges one-by-one until the graph becomes a tree diagram (AFL). Explain to students that this process demonstrates the concept of spanning trees (AOL):

• Spanning Trees (of an undirected network diagram) - a tree which includes all the vertices of the original network connected together, but not necessarily all the edges of the original network diagram.

Redraw the same graph on the whiteboard and invite another student to produce another spanning tree (AFL). Afterwards, ask students the following question (AFL):

"How many spanning trees could we draw in this diagram?"

(Vaguely, the answer is many. However, if students are interested in a precise number, Kirchhoff's Matrix Tree Theorem can be mentioned to them - the theorem allows anyone to calculate the total number of spanning trees for a given connected network diagram).

Body 1

Working Mathematically: Fluency, Communicating, Reasoning

NSW Rail Network Design (15 min) [NUM]

Briefly discuss the following question with the class (AFL):

"Why might spanning trees be useful in the real world?"

Present the following problem to the class:

The NSW State Government is requesting your assistance with designing a new, efficient rail network. The diagram (see Resource) shows you all of the possible routes between each suburb, with their travel distance in kilometres indicated. Select all of the edges we should include in our new rail network. Every suburb should be connected to this new rail network.

As a class, discuss this follow-up question (AFL):

"Whatever design we decide on, the NSW government will build it from scratch. What do they mean when they are asking for an efficient rail network?"

Give students 10 minutes to work individually, then together in their groups, to identify the most efficient rail network design. After 10 minutes, instruct one student from each group to draw their group's final design on the main whiteboard (and to include the weights in their drawing) (AFL).

Ask the class another question (AFL):

How would we compare all of these designs to see which one is the most efficient?

Have each student who visited the whiteboard to calculate the total weight of their rail network diagram (AFL). Announce the lowest weighted diagram as the best design of the class, then pose the next question to them:

"Is there an automatic way of finding the lowest weighted spanning tree?"

Advice/Differentiation Opportunities

If the main diagram (with 8 vertices) is initially too complicated for students, start them with a reduced version of the diagram with fewer vertices to consider (e.g. include only Blacktown, Parramatta, Bankstown, Liverpool and Burwood - 6 vertices and 8 edges); students can then revisit larger diagram once Prim's algorithm is known (in Body 2).

Conclusion

Working Mathematically: Communicating

Exit Task (5 min)

Provide each student with an index card. Display the following exit task on the board, then collect students' responses as they leave the classroom (AFL).

Exit Task

Draw an example of a connected network. Using that network, draw two examples of spanning trees.

Homework/Follow-up

Before students leave, show students set-up for slime mould experiment; will view results next lesson (reviewing footage).

Remind students to update their Trip Log (Tree, (Minimum) Spanning Tree, Prim's Algorithm), including writing out the steps for Prim's Algorithm (AOL). Students should also continue working on their assessment (researching & analysing a network of their choice) (AOL).

Homework:

Draw a 6 vertices simple network (should have at least 10 edges). Create a comic strip, storyboard or flip-book demonstrating Prim's algorithm (for finding the minimum spanning tree).

Bonus Task: (from Good Will Hunting) "Draw all homomorphically irreducible trees with 10 vertices", i.e. no vertices can have a degree of 2.