flownetwork

A flow network, sometimes referred to as a flownetwork, is a directed graph modeling the transfer of a commodity through a network. It consists of a set of nodes V and directed edges E, where each edge e=(u,v) has a nonnegative capacity c(e) representing the maximum amount that can be sent along that edge. Designated source s and sink t nodes define the start and end of the flow. Flow networks are a standard formalism in operations research and computer science for studying the distribution of resources, data, or traffic.

A feasible flow f assigns to each edge e a real value f(e) with 0 ≤ f(e) ≤ c(e). For every node v other than s and t, flow conservation holds: the sum of flows into v equals the sum of flows out of v. The amount of flow sent from s to t is the value |f|, equal to the net flow out of s (or into t). The objective is to maximize |f|.

To solve, one uses residual networks and augmenting path methods. The Ford-Fulkerson method and its implementations such as Edmonds-Karp and Dinic's algorithm iteratively find augmenting paths from s to t in the residual graph and increase the total flow until no augmenting path remains. The max-flow min-cut theorem states that the maximum flow value equals the total capacity of a minimum s-t cut, providing a fundamental dual perspective.

Applications include network routing, transportation planning, supply chain optimization, bipartite matching via reduction, and computer vision tasks such as image segmentation. Flow networks also serve as a teaching framework for fundamental algorithms in combinatorial optimization.