Welcome to the World of Network Flows!

Ever wondered how a city manages its traffic during rush hour, or how water reaches every house in a large town through a maze of pipes? That is exactly what Network Flows is all about! In this chapter, we will learn how to model these real-world systems to find the maximum amount of "stuff" (like cars, water, or data) that can get from a starting point to a destination. Don't worry if it sounds complicated; we will break it down step-by-step.

1. Understanding the Basics (DC1)

Before we start calculating, we need to understand the language of networks. Imagine a series of one-way streets connecting different junctions.

Key Terms:

  • Source (S): This is where the flow starts. Think of it like a water tower or a factory.
  • Sink (T): This is the final destination where the flow ends. Think of it like a kitchen tap or a warehouse.
  • Nodes: The junctions or points where the paths meet.
  • Arcs: The "pipes" or "roads" connecting the nodes. These are directed, meaning they have an arrow showing which way the flow goes.
  • Capacity: The maximum amount that an arc can carry. It is usually written as a number next to the arc. For example, a pipe with capacity \(5\) can carry up to \(5\) litres per second.
  • Flow: The actual amount currently moving through an arc. The flow can never be more than the capacity!

The Golden Rule: Conservation of Flow

In any network, what goes into a node must come out of it (except for the Source and the Sink). If \(10\) litres of water enter a junction, \(10\) litres must leave it. It can't just vanish!

Quick Review: An arc with \(3/5\) written on it means the capacity is \(5\), but the current flow is only \(3\).

Key Takeaway:

A network flow problem is basically a puzzle where we try to push as much as possible from Source to Sink without exceeding the capacities of the arcs.

2. Making the "Cut" (DC2)

A cut is a way of separating the Source from the Sink. Imagine taking a pair of scissors and literal cutting through the arcs so that there is no longer any path from \(S\) to \(T\).

How to find the Value of a Cut

The value of a cut is the sum of the capacities of all the arcs that the cut crosses, but only those going from the Source side to the Sink side.

Step-by-Step Process:

  1. Draw a line that completely separates the Source side from the Sink side.
  2. Identify every arc that your line crosses.
  3. Look at the direction of the arrows:
    • If the arrow points from the Source side towards the Sink side, add its capacity to your total.
    • If the arrow points "backwards" (from Sink side back to Source side), ignore it (its value for the cut is \(0\)).

Common Mistake: Students often add up every arc the line touches. Remember: only count the ones going "forward" from the \(S\) side to the \(T\) side!

Key Takeaway:

A cut tells us the maximum potential "throughput" at a specific boundary in the network. If we know the value of a cut is \(20\), we know for sure that the total flow can't be more than \(20\).

3. The Maximum Flow-Minimum Cut Theorem (DC3)

This sounds like a mouthful, but it is one of the most beautiful "shortcuts" in mathematics. It is the ultimate "Bottleneck Rule."

The Theorem states: The Maximum Flow in a network is equal to the Value of the Minimum Cut.

Why does this work?
Think of a funnel. You can pour as much water as you want into the top, but the amount that comes out the bottom is limited by the narrowest part (the bottleneck). In a network, the Minimum Cut is that bottleneck. It represents the tightest restriction in the entire system.

Did you know?
This theorem was famously used during the Cold War to analyze railway networks! If you want to know the most flow a network can handle, you just need to find the "cheapest" (minimum) way to cut it in half.

Key Takeaway:

If a question asks for the Maximum Flow, look for the smallest possible Cut Value you can find. That number is your answer!

4. Supersources and Supersinks (DC4)

Sometimes, life isn't simple. You might have a network with three different factories (Sources) and two different warehouses (Sinks). This looks messy, but we have a trick to fix it.

How to simplify the network:

  1. The Supersource: Create one new node called the "Supersource." Draw a directed arc from this Supersource to each of the original Sources. The capacity of these new arcs should be the total amount that each original source can produce.
  2. The Supersink: Create one new node called the "Supersink." Draw a directed arc from each of the original Sinks to this new Supersink. The capacity of these new arcs should be the maximum amount each original sink can receive.

Analogy: Imagine three small streams feeding into a lake. If you want to measure the total water, it’s easier to imagine one giant "Super-Pipe" feeding all three streams at once!

Don't worry if this seems tricky at first... Just remember that the "Super" nodes are just "imaginary" points we use to turn a complex problem into a standard one-start, one-end problem.

Key Takeaway:

Supersources and Supersinks are "dummy" nodes that allow us to use standard Max-Flow rules on networks that have multiple starting or ending points.

Chapter Summary & Quick Tips

  • Flow \( \le \) Capacity: You can't fit a gallon of water through a pint-sized pipe!
  • Conservation: Flow In = Flow Out for all middle nodes.
  • Cut Value: Only sum the capacities of forward-facing arcs (\(S \to T\)).
  • Max Flow = Min Cut: The bottleneck determines the limit.
  • Multiple starts/ends? Use a Supersource or Supersink to join them together.