Networks and Flows: Definitions and Notation
What you'll learn: You'll understand how to model flow through a network using sources, sinks, capacities, and the conservation law that governs flow at intermediate points.
The Core Idea
Imagine water flowing through a system of pipes, or data packets traveling through a computer network. A flow network is a directed graph that models such scenarios mathematically.
A flow network consists of:
- Vertices (nodes): Points where flow can enter, exit, or pass through
- Directed edges: Pipes or channels connecting vertices
- Source (s): A special vertex where flow originates (like a water pump)
- Sink (t): A special vertex where flow terminates (like a drain)
- Capacity c(u,v): The maximum amount of flow that can travel along edge (u,v)
- Flow f(u,v): The actual amount currently flowing along edge (u,v)
Flow Rules
Two fundamental constraints govern valid flows:
-
Capacity constraint: For every edge (u,v), we must have 0 ≤ f(u,v) ≤ c(u,v). You can't push more flow than the pipe allows.
-
Flow conservation: At every intermediate vertex v (neither source nor sink), the total flow entering v equals the total flow leaving v. Think of it like traffic at an intersection—if 10 cars enter per minute, 10 must leave (nothing accumulates or disappears).
Mathematically: Σ f(u,v) = Σ f(v,w) for all incoming edges (u,v) and outgoing edges (v,w).
The value of the flow is the total amount leaving the source (or equivalently, reaching the sink).
Key Takeaway: A flow network models movement through a directed graph with a source, sink, edge capacities, and flows that respect capacity limits and conserve at intermediate vertices.