Mathematics.

graph algorithms

Network Flow

Graph Theory35 minDifficulty5 out of 10

You should know: directed graphs, shortest path

Overview

A flow network is a directed graph where each edge has a capacity, and the goal is to push as much 'flow' as possible from a source vertex s to a sink vertex t without exceeding any edge's capacity, while conserving flow at every other vertex (what flows in must flow out). The maximum flow problem asks for the largest such flow value. The Ford–Fulkerson method finds it by repeatedly locating an 'augmenting path' — a path from s to t along which more flow can still be pushed — and increasing flow along it until no augmenting path remains. The max-flow min-cut theorem guarantees that this maximum flow value exactly equals the minimum total capacity of any 's-t cut' (a partition separating s from t), tying the problem to network vulnerability analysis.

Intuition

Picture a water pipe network: pipes (edges) have maximum flow rates (capacities), and you want to push as much water as possible from a reservoir (source) to a city (sink). At every junction, water in must equal water out — no accumulation. The max-flow min-cut theorem says the most water you can push through equals the capacity of the network's narrowest 'bottleneck' — the cheapest set of pipes you'd need to cut to fully separate the reservoir from the city.

Formal Definition

Definition

For a directed graph G = (V, E) with capacities c(u,v) ≥ 0, source s, and sink t, a flow f satisfies:

0≤f(u,v)≤c(u,v)∀(u,v)∈E0 \le f(u,v) \le c(u,v) \quad \forall (u,v) \in E
Capacity constraint
∑uf(u,v)=∑wf(v,w)∀v≠s,t\sum_{u} f(u,v) = \sum_{w} f(v,w) \quad \forall v \ne s,t
Flow conservation
∣f∣=∑vf(s,v)−∑vf(v,s)|f| = \sum_{v} f(s,v) - \sum_{v} f(v,s)
Value of the flow (net flow out of s)
max⁡∣f∣=min⁡(S,T)∑u∈S,v∈Tc(u,v)\max |f| = \min_{(S,T)} \sum_{u \in S, v \in T} c(u,v)
Max-flow min-cut theorem

Worked Examples

  1. Flow along the only path is limited by its smallest-capacity edge (the bottleneck).

    min⁡(5,3)=3\min(5, 3) = 3

  2. Pushing 3 units respects both capacity constraints (3 ≤ 5 and 3 ≤ 3) and no more can be pushed since A→T caps at 3.

    ∣f∣=3|f| = 3

Answer: Maximum flow = 3 (limited by the S→A→T edge of capacity 3).

Practice Problems

Difficulty 4/10

A network has a single path S→X→T with capacities S→X = 7 and X→T = 4. What is the max flow?

Difficulty 5/10

A logistics company wants to know the maximum shipping rate from a warehouse (S) to a distribution center (T) through a road network with capacity limits on each road segment. After running Ford-Fulkerson, the max flow found is 15 units. By the max-flow min-cut theorem, what can be said about the minimum-capacity set of roads that would need to be closed to fully block shipments?

Difficulty 4/10

In a flow network, vertex A (not the source or sink) has incoming flow of 6 units total. What must its total outgoing flow be, and why?

Quiz

In a flow network, at every vertex other than the source and sink, flow conservation requires:
The Ford-Fulkerson method increases flow by repeatedly finding:
The max-flow min-cut theorem states that the maximum flow value equals:

Summary

  • A flow network pushes flow from source to sink subject to edge capacities and flow conservation at intermediate vertices.
  • Ford-Fulkerson finds max flow by repeatedly augmenting along paths with spare capacity until none remain.
  • The max-flow min-cut theorem guarantees maximum flow equals the minimum total capacity of any s-t cut.

References

  1. WebsiteWikipedia — Maximum flow problem