Network Flow

Max flow, min cut, and the Ford-Fulkerson algorithm

Network Flow

Network flow models the transportation of commodities through a network from a source to a sink. Each edge has a capacity limit, and we want to maximize the total flow while respecting these constraints.

In this section, you'll learn about flow networks, the celebrated Ford-Fulkerson algorithm, the powerful max-flow min-cut theorem, and see how flow theory solves practical problems like job assignment.

What You'll Learn

🌊
Flow Networks
Sources, sinks, capacities, and conservation laws
🔄
Ford-Fulkerson
The classic algorithm for finding maximum flow
✂️
Max-Flow Min-Cut
A fundamental duality theorem in optimization
👥
Applications
Bipartite matching and job assignment

Flow Network Basics

A flow network is a directed graph where each edge has a capacity. Flow travels from a source (S) to a sink (T). Click an edge to adjust its flow!

Click an edge to select it, then use controls below to adjust flow

0
Total Flow
Valid
Conservation
Valid
Capacity
Source
Sink
Intermediate
Saturated

Flow Network Rules

  • Capacity constraint: Flow on each edge ≤ capacity
  • Flow conservation: Flow in = Flow out (except source/sink)
  • Non-negativity: Flow on each edge ≥ 0
  • The value of a flow is the total flow leaving the source

Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm finds the maximum flow by repeatedly finding augmenting paths from source to sink and pushing flow along them. This implementation uses BFS (Edmonds-Karp).

Iteration: 0Phase: Ready
0
Current Flow
0
Iterations
Running...
Status
Speed:Med

How Ford-Fulkerson Works

  1. Build the residual graph from current flow
  2. Find an augmenting path from S to T (using BFS)
  3. Find the bottleneck (minimum residual capacity on path)
  4. Augment flow by the bottleneck amount
  5. Repeat until no augmenting path exists

Max-Flow Min-Cut Theorem

The Max-Flow Min-Cut Theorem states that the maximum flow from source to sink equals the minimum capacity of any cut separating them. A cut divides vertices into two sets (S containing source, T containing sink).

0
Max Flow
?
Min Cut Capacity

About the Max-Flow Min-Cut Theorem

  • A cut (S, T) partitions vertices so S contains source, T contains sink
  • The capacity of a cut = sum of capacities of edges from S to T
  • The min cut is the cut with minimum capacity
  • Proven by Ford & Fulkerson in 1956 — a cornerstone of combinatorial optimization!

Flow Applications: Bipartite Matching

Maximum bipartite matching can be solved using max flow! Model the problem as a flow network: source connects to one set, the other set connects to sink. Each edge has capacity 1.

Job Assignment Problem

Assign workers to jobs where each worker can do at most one job and each job needs exactly one worker. Lines show which workers are qualified for which jobs.

Green edges = matched pairs in optimal solution

Toggle Qualifications (click to enable/disable):
0
Maximum Matching
9
Possible Edges

How It Works

  1. Create a source connected to all workers (capacity 1)
  2. Create edges from workers to jobs they can do (capacity 1)
  3. Connect all jobs to a sink (capacity 1)
  4. Run max flow — the flow value equals the maximum matching size!
  5. Edges with flow = 1 between workers and jobs form the matching

What We've Learned

1. Flow Networks: A directed graph with capacities on edges, a source node producing flow, and a sink node consuming flow. Flow must satisfy capacity constraints and conservation (flow in = flow out at intermediate nodes).

2. Ford-Fulkerson Algorithm: Repeatedly find augmenting paths from source to sink in the residual graph and push flow along them. The Edmonds-Karp variant uses BFS and runs in O(VE²) time.

3. Max-Flow Min-Cut Theorem: The maximum flow from source to sink equals the minimum capacity of any cut separating them. This powerful duality connects flow to graph connectivity.

4. Applications: Maximum bipartite matching reduces to max flow with unit capacities. This models job assignments, resource allocation, and many other real-world optimization problems.

Next Up: In the next section, you'll explore spectral graph theory — using eigenvalues and eigenvectors to uncover hidden structure in graphs!