Understanding Maximum Flow

Lesson Overview

Grade Level: Year 12
Curriculum Area: Mathematics – Specialist Mathematics
Unit Focus: Networks and Decision Mathematics
Specific Curriculum Link: Australian Curriculum: Specialist Mathematics – Unit 4 (ACMSM129): Solve problems using networks and graph theory, including flow capacity within directed networks.
Lesson Duration: 45 minutes
Class Size: 15 students

---

Lesson Objectives

By the end of the lesson, students should be able to:

1. Understand key components of a network (nodes, edges, capacities, source, and sink).
2. Apply the Ford-Fulkerson Algorithm to calculate the maximum flow in a directed network.
3. Understand the concept of bottlenecks in a network and their impact on maximum flow.
4. Solve real-world problems using a maximum-flow approach.

---

Materials Needed

• Whiteboard and markers
• Student laptops/tablets with graphing software (e.g., Desmos or Geogebra pre-loaded)
• Network flow handout (with diagrams and exercises)
• Projector for data visualisation
• Small coloured cards to represent a practical flow simulation activity

---

Lesson Structure

1. Introduction (5 minutes)

Teacher Prompt
"Have you ever wondered how packages from online orders get delivered so quickly? Or how water is distributed around a city? These rely on an efficient flow through networks. Today, we will explore the mathematics behind optimising flow and apply it to both abstract and real-world scenarios.”

1. Draw a simple example on the whiteboard (e.g., a network of pipes). Label the source, sink, and pipe capacities.
2. Pose guided questions: "What happens if one of these pipes becomes clogged? How do you think we can measure the maximum amount of flow through this system?"
3. Provide a brief outline of the Ford-Fulkerson Method, i.e., finding augmenting paths and residual capacities to maximise flow.

---

2. Key Concepts (10 minutes)

1. Terminology:
   Use the projector to display a pre-prepared visual with terms such as:

   • Nodes (e.g., factories, water reservoirs)
   • Edges (e.g., roads, pipes)
   • Capacity (maximum flow an edge can handle)
   • Source and sink (start and endpoint of flow).

   Briefly explain each with examples, ensuring students understand how this connects to everyday applications in logistics, transport, and water management.

2. Explanation of Maximum Flow Problem:
   Use a simple 4-node network diagram and explain step-by-step how to calculate maximum flow (do not solve in detail yet – this will come during the activity).

3. Real-world Context:
   Highlight examples in Australia, such as:

   • Sydney’s water supply network.
   • Transport bottlenecks during peak hours in inner Melbourne.
   • Internet bandwidth optimisation for a rural school network.

---

3. Interactive Activity (15 minutes)

A. Practical Demonstration – Flow Simulation (5 minutes)

Set up a "human network".

1. Arrange 6 students as nodes (label each using small name cards).
2. Use string or masking tape to create connections (edges) and assign each edge a capacity (e.g., "4 litres/second").
3. Simulate sending flow from source to sink. Choose one student to act as the "source" pouring flow, and track how much gets through to the "sink".

Introduce a bottleneck by limiting capacity on one edge, and demonstrate how this impacts the overall flow. Discuss observations briefly.

---

B. Guided Problem Solving (10 minutes)

Focus Problem: Present a pre-drawn directed network on the whiteboard (4-5 nodes, 6 edges with different capacities).

1. Work together as a class to apply the Ford-Fulkerson algorithm.
   • Step 1: Find paths from source to sink.
   • Step 2: Adjust residual capacity.
   • Step 3: Repeat until no more paths are available.

Write out the steps on the board while asking guiding questions, such as: "What is the smallest capacity in this path? How does this affect subsequent calculations?"

2. Hand out a similar follow-up problem for students to try in pairs, encouraging collaborative learning.

---

4. Reflection and Wrap-Up (5 minutes)

1. Whole-Class Discussion:

   • "What factors limited the flow in our human network simulation?"
   • Link back to real-world examples (e.g., traffic bottlenecks).

2. Quick Quiz: Pose two rapid-fire questions:

   • Identify the bottleneck in a given diagram.
   • Calculate the total maximum flow for a small network.

3. Exit Ticket Question: "How might understanding maximum flow help you in a future career?" (e.g., engineering, logistics, IT).

---

Differentiation Strategies

1. For Advanced Students: Provide a more complex network diagram with multiple augmenting paths for independent exploration.
2. For Students Needing Support: Pair them with a peer mentor during the problem-solving activity. Simplify the network diagram or provide scaffolded hints.

---

Assessment Opportunities

• Observation during the practical flow simulation (participation and understanding).
• Marking of pair work during the guided problem activity.
• Responses to exit ticket questions to gauge conceptual understanding.

---

Teacher Reflection

• What worked: Did students actively engage with the physical simulation and problem-solving exercises? Were the objectives clear and achieved?
• What to improve: Were there challenges in applying Ford-Fulkerson? Can visuals or scaffolding for future lessons make it clearer?

---

Extension Ideas

In a follow-up lesson, you could explore minimum cut problems in networks or dive deeper into practical Australian contexts, such as using maximum flow concepts to optimise energy systems or supply chain logistics.