Welcome to Flows in Networks!
In this chapter, we are going to learn how to manage "traffic" through a system. Whether it is water in pipes, data on the internet, or cars on a motorway, the goal is the same: How can we move as much as possible from the start to the finish without breaking the system?
This is a core part of Decision Mathematics 2, and it’s actually quite satisfying once you get the hang of the "labelling" rhythm. Don't worry if it looks like a mess of arrows and numbers at first—we will break it down step-by-step!
1. The Anatomy of a Network
Before we start flowing, we need to know what we are looking at. In this syllabus, we only deal with directed arcs (arrows showing the direction of flow).
- Source (S): Where the flow starts (the "tap").
- Sink (T): Where the flow ends (the "drain").
- Capacity: The maximum amount an arc can carry. Think of this as the width of a pipe.
- Feasible Flow: A flow that follows two rules:
1. It doesn't exceed the capacity of any arc.
2. Conservation of Flow: What goes into a vertex must come out (unless it's the Source or Sink).
Quick Review: If 10 liters go into a junction, 10 liters must come out. You can't just lose water in the middle of the network!
2. Cuts and Their Capacity
A cut is like an imaginary line that completely separates the Source from the Sink. If you "cut" these arcs, no flow can reach the end.
How to Calculate Cut Capacity
To find the capacity of a cut, you sum the capacities of the arcs that cross the cut pointing from the Source side to the Sink side.
Common Mistake to Avoid: If an arc crosses the cut going backwards (from the Sink side toward the Source side), we ignore its capacity. We only care about what’s helping the flow reach the Sink!
Key Takeaway: Capacity of a Cut = \(\sum (\text{capacities of arcs crossing Source } \rightarrow \text{ Sink})\).
3. The Labelling Procedure
This is the "meat" of the chapter. We use this to augment (increase) a flow until we find the maximum possible flow. Imagine you have a half-full pipe system; this procedure helps you find the "gaps" to squeeze more through.
The Two Arrows
On each arc, we use a label with two numbers and two arrows:
- Forward Arrow (\(\rightarrow\)): This shows how much more flow we can add. It is \(\text{Capacity} - \text{Current Flow}\).
- Backward Arrow (\(\leftarrow\)): This shows how much flow we could remove or redirect. It is simply the \(\text{Current Flow}\).
Step-by-Step Augmentation
- Find a path: Look for any path from S to T where all forward arrows are greater than zero.
- Determine the increase: Find the smallest forward arrow on that path. Let’s call this value \(x\).
- Update the labels:
- For each arc on the path, subtract \(x\) from the forward arrow.
- For each arc on the path, add \(x\) to the backward arrow. - Repeat: Keep doing this until there are no more paths with available "forward" room from S to T.
Did you know? Even if an arc looks "full" in one direction, you can sometimes "push back" flow through a backward arrow to open up a better route elsewhere!
4. The Max-Flow Min-Cut Theorem
This is a famous rule in Decision Maths. It states that:
The Maximum Flow through a network is equal to the Minimum Cut capacity.
If you find a flow (using the labelling procedure) and you can also find a cut that has the exact same capacity value, you have proven that your flow is the maximum possible.
Key Takeaway: To prove you've found the Max Flow, look for the "bottleneck" in the network. That bottleneck is your Min Cut.
5. Handling Variations
Sometimes the exam will give you a "messy" network. Here is how to tidy it up:
Multiple Sources and Sinks (3.4)
If you have three factories (Sources) and two shops (Sinks), don't panic!
- Create a Super-Source and draw arcs from it to the real sources. The capacity of these new arcs is the total capacity the factories can produce.
- Create a Super-Sink and draw arcs from the real sinks to it.
Restricted Vertex Capacity (3.4)
Sometimes a junction (vertex) can only handle a certain amount of flow (e.g., a pumping station that can only process 50 units).
The Trick: Split the vertex into two! Vertex \(V\) becomes \(V_{in}\) and \(V_{out}\). Connect them with a single arc with the capacity of the vertex.
Analogy: Think of a nightclub. The "Vertex" is the door. To model the capacity of the door, you have to pass from "Outside the door" (\(V_{in}\)) through the "ID check" (the capacity arc) to "Inside the club" (\(V_{out}\)).
6. Lower Capacities (3.5)
In most problems, the lower limit of flow is zero. But sometimes an arc must carry a minimum amount (a lower capacity).
In these cases, the flow \(f\) on an arc must satisfy:
\(\text{Lower Capacity} \leq f \leq \text{Upper Capacity}\)
When checking for a "feasible flow" here, you must ensure every single arc stays within its specific boundaries.
Common Mistakes to Avoid
- The "Backwards" Cut: Adding arc capacities that point back toward the source when calculating a cut. Don't do it!
- Arithmetic Errors: It is so easy to miscalculate when adding/subtracting on the labels. Double-check your subtraction during augmentation.
- Missing a Path: Always scan the network carefully. Sometimes a path involving a "backward" arrow is the only way to reach the maximum flow.
Final Encouragement: Decision Mathematics is all about following the algorithm. Keep your diagrams neat, use a pencil so you can rub out labels, and remember the golden rule: Inflow = Outflow! You've got this.