Understanding Maximum Flow

Curriculum Alignment

This lesson is designed for Year 12 Mathematics and aligns with the Australian Curriculum: Mathematical Methods, focusing on networks and decision mathematics under the topic of optimisation problems. Specifically, we will explore graph theory and flow networks, introducing the concepts of network capacity and flow intuitively before applying the Max-Flow Min-Cut theorem in later lessons.

---

Lesson Overview

• Learning Objectives:

  • Understand the concept of maximum flow through a network using real-world analogies and hands-on activities.
  • Visualise how flow is constrained by capacities of individual edges in a network.
  • Build an intuitive understanding of bottlenecks and their effect on overall flow.

• Success Criteria:

  • Students can explain what maximum flow is in their own words.
  • Students can identify "bottleneck edges" in a network and explain their importance.
  • Students confidently engage in solving a network flow puzzle using logical reasoning.

• Class Size: 6 students

• Duration: 40 minutes

---

Lesson Plan

1. Engage – Real-World Analogy: Water Through Pipes (5 minutes)

1. Start by asking:
   • "Has anyone ever tried to water their garden using a hosepipe with kinks, or a series of connected hoses of different thicknesses? What happens to the water flow?"
   • Discuss how the maximum flow of water depends on the narrowest section of the hoses.
2. Using a diagram on the whiteboard, draw a network of interconnected hoses, each with a labelled "capacity" (e.g., 5 litres/min, 10 litres/min).
3. Explain that this is an example of a flow network—where we move something (in this case, water) from a source point to a destination point while being constrained by the "capacities" of the paths it can travel.

---

2. Explore – Hands-On Activity: Human Network Simulation (10 minutes)

1. Setup the Scenario:

   • Arrange the students as "nodes" in a physical network around the classroom. Use sticky notes or mini whiteboards to label their edges with specific capacities.
   • Example network:
     • Node A (Source) → Node B: 8 units.
     • Node A → Node C: 6 units.
     • Node B → Node D (Sink): 4 units.
     • Node C → Node D: 3 units.
   • Have two additional students play the roles of "source" (sending flow) and "sink" (receiving flow).

2. Activity Instructions:

   • Students must "move" flow units (use poker chips, counters, or simply keep count verbally) from Source A to Sink D, respecting the capacities of the edges.
   • Students try different paths until they achieve maximum flow.

3. Probe students with guiding questions:

   • "Why can’t more flow be sent down this path?"
   • "What happens when one of the paths becomes full?"
   • "Can you find another path to increase the total flow?"

4. Once the maximum flow is identified, discuss its value and how the "bottleneck" edges limited the overall flow.

---

3. Explain – Visualising Network Flow (10 minutes)

1. Return to the whiteboard and redraw the human network used in the activity, replacing people with nodes and counters with arrows representing flow.

   • Label flow values, e.g., Flow / Capacity such as 4 / 8.

2. Explain the concept of residual capacity:

   • "If 4 units are flowing along an edge with 8 capacity, 4 units of extra capacity are still available."

3. Highlight the role of bottlenecks:

   • Use the smallest capacity edge (e.g., 3 / 3) to emphasise how it constrains the entire system.
   • Introduce the idea that identifying these bottlenecks will help later when learning the Max-Flow Min-Cut theorem.

---

4. Elaborate – Group Problem: Flow Network Puzzle (10 minutes)

Distribute a worksheet or present a diagram on the board featuring a new network with nodes, edges, and edge capacities.

• Challenge students to work together to calculate the maximum flow for this network, using the concepts already discussed.
• Provide the following hints to scaffold their reasoning:
  • Start by trying different paths and adding up the flow.
  • Look for bottleneck edges.
  • Think of the activity they just completed.

Walk around, observe their progress, and provide encouragement or subtle guidance when needed.

---

5. Evaluate – Reflection and Informal Quiz (5 minutes)

Wrap up the lesson with a quick reflective discussion or mini-quiz:

1. Reflection Questions for Students:

   • "What did you notice about how flow is limited in a network?"
   • "How does understanding flow help with solving real-world problems, like traffic congestion or data transfer?"

2. Quiz Questions to Answer in Pairs:

   • Define maximum flow in your own words.
   • If a network has an edge with a capacity of 0, how does that affect flow?
   • Why is it important to find bottlenecks in a network?

---

Differentiation Strategies

• For advanced students:

  • Pose questions about optimising flow through more complex networks with directed edges.
  • Introduce the concept of augmenting paths briefly.

• For students needing more support:

  • Pair them with peers for the hands-on activity.
  • Provide a smaller, simpler network problem for the worksheet.

---

Materials Needed

1. Whiteboard and markers for diagrams.
2. Sticky notes or mini whiteboards to label edges for the human network simulation.
3. Poker chips or counters (optional) to represent flow units.
4. Worksheet or pre-drawn network diagram for group problem activity.

---

Teacher Reflection and Feedback

At the end of the lesson, reflect on the following:

• Were students able to intuitively understand the concept of flow and its constraints?
• Did the hands-on activity engage students and aid their understanding?
• Were students able to identify bottlenecks and relate them to the flow capacity of the network?

Consider following up this lesson with an introduction to the Max-Flow Min-Cut theorem, leveraging their newfound understanding of bottleneck edges.