Network Flow Basics

Graph Theory · Axiom Academy

LESSON Network Flow Fundamentals Understanding flow networks, capacity constraints, flow conservation, and how to measure the value of a flow in directed graphs. c(u, v): Capacity function for each edge (u, v) where c(u, v) ≥ 0 s: Source vertex (where flow originates) t: Sink vertex (where flow terminates) Each edge has a non-negative capacity representing the maximum amount of flow that can pass through it. Think of water pipes, network bandwidth, or road traffic capacity. Every flow network has exactly one source and one sink : All other vertices are internal nodes where flow must be conserved: what flows in must equal what flows out. For a flow f to be valid, it must respect capacity constraints on every edge: f(u, v): The flow on edge (u, v) c(u, v): The capacity of edge (u, v) The flow on any edge cannot be negative (flows don't go backwards) and cannot exceed the edge's capacity. Watch how flow respects these boundaries: At every internal node (neither source nor sink), flow must be conserved : This is analogous to Kirchhoff's current law in electrical circuits: charge (flow) cannot accumulate at a node. Everything that enters must leave. The value of a flow |f| measures the total amount of flow from source to sink: The flow value represents the net flow leaving the source (or equivalently, the net flow entering the sink). In optimization problems, we often want to find the maximum flow : the largest possible flow value for a given network.

This is the written version of the interactive lesson above. See the full Graph Theory course.