Welcome to Flows in Networks!

Hello there! Welcome to one of the most practical chapters in Decision Mathematics 2. Have you ever wondered how water companies ensure everyone gets enough water during a heatwave, or how internet data travels from a server to your phone without crashing? That is exactly what Flows in Networks is about!

In this chapter, we are going to learn how to model these systems using "networks" and find the absolute maximum amount of "stuff" (water, data, cars) that can move from a starting point to an ending point. Don't worry if it seems like a lot of lines and numbers at first—we’ll break it down step-by-step!

1. The Basics: What is a Flow Network?

Before we start "cutting" things or "labelling" nodes, let’s make sure we understand the map we are looking at. A flow network is a directed graph (a collection of points connected by arrows) where each arrow has a limit.

Key Terms to Know:

  • Source (S): The starting point where everything comes from (like a water reservoir).
  • Sink (T): The destination where everything is going (like your kitchen tap).
  • Arc (or Edge): The pipes or roads connecting the points. In this syllabus, we only look at directed arcs (one-way streets).
  • Capacity: The maximum amount of flow an arc can handle. For example, if an arc has a capacity of \(10\), you can't send \(11\) units through it.
  • Flow: The actual amount currently moving through an arc.

Quick Review: Think of a network like a plumbing system. The capacity is the width of the pipe, and the flow is the actual water running through it.

Important Rule: At every node (except the Source and Sink), Flow In = Flow Out. You can't just lose water in the middle of a pipe!

Key Takeaway: A network shows how much "stuff" can move from Source (S) to Sink (T) based on the capacity of the one-way paths between them.

2. Cuts and Their Capacity

Imagine you wanted to stop all flow from getting to the Sink. Where would you use your scissors to "cut" the network? In math, a cut is a way of splitting the network into two separate pieces.

What is a Cut?

A cut partitions the vertices into two sets: Set X (which contains the Source \(S\)) and Set Y (which contains the Sink \(T\)). To be a valid cut, every path from \(S\) to \(T\) must be broken.

Calculating the Capacity of a Cut

This is where many students get tripped up, so pay close attention! The capacity of a cut is the sum of the capacities of the arcs that go from Set X to Set Y.

Common Mistake to Avoid: If an arc goes "backwards" (from Set Y back to Set X), we ignore its capacity when calculating the cut's value. We only care about the pipes trying to cross the "wall" toward the sink.

Analogy: Imagine Set X is "Home" and Set Y is "The Shop." If you are building a fence to stop people getting to the shop, you only care about the gates that let people go forward. You don't count the gates that only let people walk back home!

Did you know? The capacity of any cut is always greater than or equal to the value of any flow. This leads us to a very famous theorem later on!

Key Takeaway: Capacity of a Cut = Sum of capacities of arcs crossing from the Source side (X) to the Sink side (Y). Ignore any arcs pointing backwards.

3. The Labelling Procedure (Flow Augmentation)

Now we get to the "doing" part! How do we actually increase the flow in a network? We use a labelling procedure to find "breakthrough" paths.

Step-by-Step: How to Augment Flow

1. Find an initial flow: Often, you'll be given a starting flow. Check that Flow In = Flow Out at every node.
2. Look for a path: Find a path from \(S\) to \(T\) that isn't full yet.
3. Use the Labels: At each node, we use arrows to show how much we can change the flow:
    • Forward Arrow: Points in the same direction as the arc. It shows how much extra flow the arc can take (Capacity - Current Flow).
    • Backward Arrow: Points opposite to the arc. It shows how much flow we could remove from that arc (Current Flow).
4. Increase the flow: Find the smallest "potential" on your chosen path and add that amount to the flow along the whole path.
5. Repeat: Keep doing this until you can no longer find a path from \(S\) to \(T\).

Memory Aid: If you find it hard to remember which way the arrows go, just remember: "Forward to fill, Backward to spill."

Key Takeaway: We use labels to see where we have "space" left in the pipes. Once no more paths can be found with "space" available, we've reached the Max Flow!

4. The Max-Flow Min-Cut Theorem

This is the "Golden Rule" of flows. It’s a powerful tool that helps us prove we’ve found the best possible answer.

The Theorem: In any network, the Maximum Flow value is equal to the Minimum Cut capacity.

How to use this in an exam:

If an exam question asks you to "Prove that your flow is maximal," you should:
1. State the value of your final flow.
2. Find a cut in the network that has exactly the same capacity as your flow value.
3. Mention the Max-Flow Min-Cut Theorem. If Flow = Cut Capacity, then the flow must be the maximum possible.

Don't worry if this seems tricky at first! Finding the "Minimum Cut" is often like finding a bottleneck. Look for the part of the network where all the pipes are completely full (saturated). That's usually where the minimum cut is hidden!

Quick Review Box:
• Max Flow = Largest amount of stuff moved.
• Min Cut = Smallest "bottleneck" capacity.
• They are always equal at the end!

Key Takeaway: The "bottleneck" (Minimum Cut) limits the total amount of "traffic" (Maximum Flow) that can pass through the system.

Summary Checklist

Before you move on to practice questions, make sure you can:
• Identify the Source and Sink.
• Calculate the capacity of a cut (remembering to ignore backwards arcs!).
• Use labelling to increase the flow along a path.
• Use the Max-Flow Min-Cut Theorem to verify your final answer.

You've got this! Flows in networks might look like a messy web at first, but once you find the paths and the bottlenecks, it all clicks into place like a perfect puzzle.