Flow Networks and Definitions
What you'll learn: You'll understand how flow networks model real-world transport systems using directed graphs with capacity constraints.
What Is a Flow Network?
A flow network is a directed graph designed to model the movement of "stuff" (water, data, traffic, goods) from a starting point to an ending point. Think of it like a city's water pipe system: water flows from a reservoir through pipes of different sizes to homes.
Formally, a flow network consists of:
- A directed graph G = (V, E)
- A source vertex s (where flow originates)
- A sink vertex t (where flow terminates)
- A capacity function c(u, v) ≥ 0 for each edge (u, v), representing the maximum flow that edge can carry
The Flow Function
The flow is a function f(u, v) on edges that represents how much is actually flowing through each edge, subject to two key rules:
-
Capacity constraint: For every edge (u, v), the flow cannot exceed capacity:
0 ≤ f(u, v) ≤ c(u, v) -
Flow conservation: For every vertex except s and t, flow in equals flow out: ∑(flow in) = ∑(flow out)
Intuitive Example
Imagine a highway network:
- Source (s): City center where all traffic starts
- Sink (t): Suburbs where everyone goes
- Capacities: Lane counts on roads (2-lane road = capacity 2000 cars/hour)
- Flow: Actual cars traveling each road segment
The flow can't exceed road capacity, and at every intersection (except start/end), cars entering must equal cars leaving.
Key Takeaway: Flow networks model transport through directed graphs with capacities, where flow must respect capacity limits and conserve at intermediate vertices.