Flow network
In graph theory and computer science, a flow network is a directed graph G = (V, E) with a distinguished source vertex s and sink vertex t, where each edge (u, v) \in E is assigned a nonnegative capacity c(u, v) representing the maximum amount of a commodity that can flow through it, and the goal is typically to compute a feasible flow f from s to t that respects these capacities while maximizing the total flow value.[1] A feasible flow must satisfy three properties: conservation of flow at intermediate vertices (inflow equals outflow), nonnegativity (f(u, v) \geq 0), and capacity constraints ($0 \leq f(u, v) \leq c(u, v)).[2] The maximum flow problem, which seeks the highest possible flow value from s to t, is a foundational optimization challenge in this framework, closely related to the min-cut problem via the max-flow min-cut theorem stating that the maximum flow equals the minimum capacity of any s- t cut.[1] The concept of flow networks originated in the mid-20th century, with the seminal work by L. R. Ford Jr. and D. R. Fulkerson introducing the Ford-Fulkerson algorithm in 1956, which computes maximum flows by iteratively finding augmenting paths in the residual graph until no such path exists.[3] Subsequent improvements include the Edmonds-Karp algorithm (1972), a breadth-first search implementation of Ford-Fulkerson achieving polynomial time complexity O(VE^2), and faster methods like Dinic's algorithm (1970) with time complexity O(V^2E) for general graphs.[1] These algorithms underpin efficient solutions to flow problems, with modern variants addressing unit capacities, high precision, or parallel computation for large-scale networks.[4] Flow networks have broad applications across operations research, engineering, and computer science, modeling scenarios involving resource allocation and constraint satisfaction.[5] Notable uses include transportation systems for optimizing traffic or shipment routing, bipartite matching for assigning jobs to workers or edges in matchings, image segmentation in computer vision by partitioning pixels based on flow cuts, and network reliability analysis to ensure fault-tolerant connectivity.[6][7] In distributed computing, they help solve problems like egalitarian resource distribution or open-pit mining optimization, while extensions to minimum-cost flows incorporate edge costs for scenarios like airline scheduling.[8][9]Core Definitions
Graph Structure
A flow network is defined as a directed graph G = (V, E), consisting of a finite set of vertices V and a set of directed edges E \subseteq V \times V, where each edge represents a directed arc from one vertex to another.[10] This structure models the topology of systems where resources or commodities can move unidirectionally between nodes, such as in transportation or communication networks. The foundational formulation of this graph-theoretic framework appears in the work of Ford and Fulkerson, who introduced it to analyze maximal flows in rail networks represented as directed connections between cities.[11] Central to the flow network are two designated terminal vertices: the source s \in V and the sink t \in V, with s \neq t. The source serves as the origin point for the flow, while the sink acts as the destination, defining the direction and purpose of potential movements through the graph. Arcs are denoted as ordered pairs (u, v) with u, v \in V and u \neq v, capturing the one-way nature of connections.[10] Standard flow networks assume finite capacities on arcs for the core maximum flow problems, though formulations allowing infinite capacities are used in certain extensions to represent unconstrained paths.[12] Additionally, these networks typically exclude self-loops (arcs of the form (u, u)) and parallel arcs between the same pair of vertices, ensuring a simple directed graph structure unless explicitly stated otherwise; such assumptions simplify analysis without loss of generality for most applications.[13]Capacities and Terminals
In a flow network, which builds upon a directed graph G = (V, E), each arc (u, v) \in E is assigned a capacity that limits the amount of flow it can carry. The capacity function c: E \to \mathbb{R}_{\geq 0} maps each arc to a non-negative real number, representing the maximum allowable flow along that arc.[14][1] Capacities are typically fixed at the outset of the problem, providing the static constraints within which flow computations occur.[14] To handle cases where an arc imposes no practical limit, the capacity may be denoted as c(u, v) = \infty, indicating an unbounded arc.[14] If there is no arc from u to v (i.e., (u, v) ∉ E), then c(u, v) = 0, ensuring capacities align with the graph's structure.[14][1] The network designates two special vertices: a source s \in V as the origin of net outflow and a sink t \in V as the destination of net inflow, which together frame the directional flow from start to end.[14][1] These terminals are fixed prior to any flow assignment, establishing the problem's boundaries.[14]Flow Fundamentals
Valid Flow Assignment
A valid flow assignment in a flow network is defined by a function f: E \to \mathbb{R}_{\geq 0}, which assigns a non-negative real number f(u,v) to each arc (u,v) \in E, representing the rate or amount of flow traversing that arc. This function ensures that flow values are directed along the existing arcs of the network, with f(u,v) > 0 only if the arc (u,v) is present in E; otherwise, f(u,v) = 0 for non-existent arcs.[15][16] The core property of a valid flow assignment is adherence to capacity constraints on each arc. Specifically, for every arc (u,v) \in E, the flow must satisfy $0 \leq f(u,v) \leq c(u,v), where c(u,v) is the capacity of the arc, preventing any overload or negative flow.[15][17] This bound ensures that the assignment respects the physical or logical limits of the network edges, such as bandwidth in communication systems or throughput in transportation models. In formulations that extend the flow function to all vertex pairs for consistency with residual networks, skew symmetry is imposed: f(u,v) = -f(v,u) for all vertices u, v \in V. This antisymmetric property facilitates the handling of potential reverse flows in augmentation processes, while maintaining non-negativity in the forward direction where arcs exist.[16] An example of an invalid flow assignment occurs when f(u,v) > c(u,v) for any arc (u,v), such as assigning 15 units of flow to an arc with a capacity of 10; this violates the capacity constraint and renders the assignment infeasible.[15][17]Flow Conservation
In a flow network, the conservation property requires that, for every vertex v that is neither the source s nor the sink t, the total inflow equals the total outflow. This ensures that the commodity being transported—such as freight, data, or fluid—neither accumulates nor dissipates at intermediate nodes. The flow function f, which assigns non-negative values to arcs subject to capacity constraints, must satisfy this balance to qualify as a valid flow. Mathematically, the conservation condition is given by \sum_{\substack{u \\ (u,v) \in E}} f(u,v) = \sum_{\substack{w \\ (v,w) \in E}} f(v,w) for all vertices v \neq s, t, where E denotes the set of directed edges in the network. This equation holds as a defining constraint for feasible flows, ensuring the network's integrity. At the source s, the net flow is positive (outflow exceeds inflow), representing the origin of the commodity, while at the sink t, the net flow is negative (inflow exceeds outflow), indicating the destination. Exceptions to the balance thus occur only at these terminals. The conservation property originates from physical principles, modeling scenarios where quantities like mass, energy, or resources are preserved during transport, as in rail freight networks or pipeline systems. In the seminal formulation, it captures the steady-state movement of commodities through interconnected paths without loss at junctions. To verify that conservation holds in feasible flows, consider the algebraic structure: the flow f is constructed to satisfy the linear equality constraints above alongside capacity bounds $0 \leq f(e) \leq c(e) for each edge e with capacity c(e). Any solution to this system of equations inherently upholds the balance at non-terminal vertices by definition, as deviations would violate the feasibility conditions. This can be confirmed by substituting the flow values into the summation equations, yielding equality for each qualifying v.Net Flow and Value
In flow networks, the net flow out of the source vertex s for a given flow assignment f captures the total amount of flow originating from s, accounting for both outgoing and any incoming flows on edges incident to s. Formally, it is defined as|f|(s) = \sum_{v : (s,v) \in E} f(s, v) - \sum_{u : (u,s) \in E} f(u, s),
where E denotes the set of edges in the network.[1] This formulation ensures that the net contribution from the source is precisely measured, even in networks where s might have incoming edges, though standard constructions often assume no such edges exist to simplify the model.[18] The value of the flow, denoted |f|, is equivalently defined as this net flow out of the source. By the conservation law, which requires that inflow equals outflow at every non-terminal vertex, the flow value also equals the net flow into the sink vertex t, given by
|f|(t) = \sum_{v : (v,t) \in E} f(v, t) - \sum_{u : (t,u) \in E} f(t, u).
In the common case where the source has no incoming edges and the sink has no outgoing edges, the value simplifies to |f| = \sum_{v} f(s, v), directly representing the aggregate outflow from s. This equivalence underscores the global balance enforced by local conservation, ensuring that the total flow generated at the source ultimately reaches the sink.[1][18] The maximum flow problem centers on finding a valid flow f that maximizes the flow value |f|, while adhering to edge capacity constraints $0 \leq f(e) \leq c(e) for all edges e and the conservation property at intermediate vertices. This optimization objective quantifies the network's overall throughput capacity from source to sink under the given constraints.[19][1] Within this framework, an edge (u, v) is saturated if f(u, v) = c(u, v), indicating that the edge is operating at its full capacity and cannot accommodate additional forward flow without violating constraints. Saturation plays a key role in assessing whether a flow is maximal, as it highlights bottlenecks in the network's structure.[18]