Hubbry Logo
Flow networkFlow networkMain
Open search
Flow network
Community hub
Flow network
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Flow network
Flow network
Flow network
View on Wikipedia
from Wikipedia

In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, image segmentation, and the matching problem.

Sample Figure: A flow network showing flow and capacity

Definition

[edit]

A network is a directed graph G = (V, E) with a non-negative capacity function c for each edge, and without multiple arcs (i.e. edges with the same source and target nodes). Without loss of generality, we may assume that if (u, v) ∈ E, then (v, u) is also a member of E. Additionally, if (v, u) ∉ E then we may add (v, u) to E and then set the c(v, u) = 0.

If two nodes in G are distinguished – one as the source s and the other as the sink t – then (G, c, s, t) is called a flow network.[1]

Flows

[edit]

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such as what is the maximum number of units that can be transferred from the source node s to the sink node t? The amount of flow between two nodes is used to represent the net amount of units being transferred from one node to the other.

The excess function xf : V → ℝ represents the net flow entering a given node u (i.e. the sum of the flows entering u) and is defined byA node u is said to be active if xf (u) > 0 (i.e. the node u consumes flow), deficient if xf (u) < 0 (i.e. the node u produces flow), or conserving if xf (u) = 0. In flow networks, the source s is deficient, and the sink t is active. Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

A pseudo-flow is a function f of each edge in the network that satisfies the following two constraints for all nodes u and v:
  • Skew symmetry constraint: The flow on an arc from u to v is equivalent to the negation of the flow on the arc from v to u, that is: f (u, v) = −f (v, u). The sign of the flow indicates the flow's direction.
  • Capacity constraint: An arc's flow cannot exceed its capacity, that is: f (u, v) ≤ c(u, v).
A pre-flow is a pseudo-flow that, for all v ∈ V \{s}, satisfies the additional constraint:
  • Non-deficient flows: The net flow entering the node v is non-negative, except for the source, which "produces" flow. That is: xf (v) ≥ 0 for all v ∈ V \{s}.
A feasible flow, or just a flow, is a pseudo-flow that, for all v ∈ V \{s, t}, satisfies the additional constraint:
  • Flow conservation constraint: The total net flow entering a node v is zero for all nodes in the network except the source s and the sink t, that is: xf (v) = 0 for all v ∈ V \{s, t}. In other words, for all nodes in the network except the source s and the sink t, the total sum of the incoming flow of a node is equal to its outgoing flow (i.e. , for each vertex v ∈ V \{s, t}).

The value |f| of a feasible flow f for a network, is the net flow into the sink t of the flow network, that is: |f| = xf (t). Note, the flow value in a network is also equal to the total outgoing flow of source s, that is: |f| = −xf (s). Also, if we define A as a set of nodes in G such that s ∈ A and t ∉ A, the flow value is equal to the total net flow going out of A (i.e. |f| = f out(A) − f in(A)).[2] The flow value in a network is the total amount of flow from s to t.

Concepts useful to flow problems

[edit]

Flow decomposition

[edit]

Flow decomposition[3] is a process of breaking down a given flow into a collection of path flows and cycle flows. Every flow through a network can be decomposed into one or more paths and corresponding quantities, such that each edge in the flow equals the sum of all quantities of paths that pass through it. Flow decomposition is a powerful tool in optimization problems to maximize or minimize specific flow parameters.

Adding arcs and flows

[edit]

We do not use multiple arcs within a network because we can combine those arcs into a single arc. To combine two arcs into a single arc, we add their capacities and their flow values, and assign those to the new arc:

  • Given any two nodes u and v, having two arcs from u to v with capacities c1(u,v) and c2(u,v) respectively is equivalent to considering only a single arc from u to v with a capacity equal to c1(u,v)+c2(u,v).
  • Given any two nodes u and v, having two arcs from u to v with pseudo-flows f1(u,v) and f2(u,v) respectively is equivalent to considering only a single arc from u to v with a pseudo-flow equal to f1(u,v)+f2(u,v).

Along with the other constraints, the skew symmetry constraint must be remembered during this step to maintain the direction of the original pseudo-flow arc. Adding flow to an arc is the same as adding an arc with the capacity of zero.[citation needed]

Residuals

[edit]

The residual capacity of an arc e with respect to a pseudo-flow f is denoted cf, and it is the difference between the arc's capacity and its flow. That is, cf (e) = c(e) − f(e). From this we can construct a residual network, denoted Gf (V, Ef), with a capacity function cf which models the amount of available capacity on the set of arcs in G = (V, E). More specifically, capacity function cf of each arc (u, v) in the residual network represents the amount of flow which can be transferred from u to v given the current state of the flow within the network.

This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network.

Note that there can be an unsaturated path (a path with available capacity) from u to v in the residual network, even though there is no such path from u to v in the original network.[citation needed] Since flows in opposite directions cancel out, decreasing the flow from v to u is the same as increasing the flow from u to v.

Augmenting paths

[edit]

An augmenting path is a path (u1, u2, ..., uk) in the residual network, where u1 = s, uk = t, and for all ui, ui + 1 (cf (ui, ui + 1) > 0) (1 ≤ i < k). More simply, an augmenting path is an available flow path from the source to the sink. A network is at maximum flow if and only if there is no augmenting path in the residual network Gf.

The bottleneck is the minimum residual capacity of all the edges in a given augmenting path.[2] See example explained in the "Example" section of this article. The flow network is at maximum flow if and only if it has a bottleneck with a value equal to zero. If any augmenting path exists, its bottleneck weight will be greater than 0. In other words, if there is a bottleneck value greater than 0, then there is an augmenting path from the source to the sink. However, we know that if there is any augmenting path, then the network is not at maximum flow, which in turn means that, if there is a bottleneck value greater than 0, then the network is not at maximum flow.

The term "augmenting the flow" for an augmenting path means updating the flow f of each arc in this augmenting path to equal the capacity c of the bottleneck. Augmenting the flow corresponds to pushing additional flow along the augmenting path until there is no remaining available residual capacity in the bottleneck.

Multiple sources and/or sinks

[edit]

Sometimes, when modeling a network with more than one source, a supersource is introduced to the graph.[4] This consists of a vertex connected to each of the sources with edges of infinite capacity, so as to act as a global source. A similar construct for sinks is called a supersink.[5]

Example

[edit]
Figure 1: A flow network showing flow and capacity

In Figure 1 you see a flow network with source labeled s, sink t, and four additional nodes. The flow and capacity is denoted . Notice how the network upholds the capacity constraint and flow conservation constraint. The total amount of flow from s to t is 5, which can be easily seen from the fact that the total outgoing flow from s is 5, which is also the incoming flow to t. By the skew symmetry constraint, from c to a is -2 because the flow from a to c is 2.

Figure 2: Residual network for the above flow network, showing residual capacities

In Figure 2 you see the residual network for the same given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero in Figure 1, for example for the edge . This network is not at maximum flow. There is available capacity along the paths , and , which are then the augmenting paths.

The bottleneck of the path is equal to .

Applications

[edit]
See also: Pipe network analysis

Picture a series of water pipes, fitting into a network. Each pipe is of a certain diameter, so it can only maintain a flow of a certain amount of water. Anywhere that pipes meet, the total amount of water coming into that junction must be equal to the amount going out, otherwise we would quickly run out of water, or we would have a buildup of water. We have a water inlet, which is the source, and an outlet, the sink. A flow would then be one possible way for water to get from source to sink so that the total amount of water coming out of the outlet is consistent. Intuitively, the total flow of a network is the rate at which water comes out of the outlet.

Flows can pertain to people or material over transportation networks, or to electricity over electrical distribution systems. For any such physical network, the flow coming into any intermediate node needs to equal the flow going out of that node. This conservation constraint is equivalent to Kirchhoff's current law.

Flow networks also find applications in ecology: flow networks arise naturally when considering the flow of nutrients and energy between different organisms in a food web. The mathematical problems associated with such networks are quite different from those that arise in networks of fluid or traffic flow. The field of ecosystem network analysis, developed by Robert Ulanowicz and others, involves using concepts from information theory and thermodynamics to study the evolution of these networks over time.

Classifying flow problems

[edit]

The simplest and most common problem using flow networks is to find what is called the maximum flow, which provides the largest possible total flow from the source to the sink in a given graph. There are many other problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as bipartite matching, the assignment problem and the transportation problem. Maximum flow problems can be solved in polynomial time with various algorithms (see table). The max-flow min-cut theorem states that finding a maximal network flow is equivalent to finding a cut of minimum capacity that separates the source and the sink, where a cut is the division of vertices such that the source is in one division and the sink is in another.

Well-known algorithms for the Maximum Flow Problem
Inventor(s) Year Time
complexity
(with n nodes
and m arcs)
Dinic's algorithm 1970 O(mn2)
Edmonds–Karp algorithm 1972 O(m2n)
MPM (Malhotra, Pramodh-Kumar, and Maheshwari)
algorithm[6] 		1978 O(n3)
Push–relabel algorithm (Goldberg & Tarjan) 1988 O(n2m)
James B. Orlin[7] 2013 O(mn)
Li Chen, Rasmus Kyng, Yang P. Liu,

Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva

2022

In a multi-commodity flow problem, you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the same transportation network.

In a minimum cost flow problem, each edge has a given cost , and the cost of sending the flow across the edge is . The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In a circulation problem, you have a lower bound on the edges, in addition to the upper bound . Each edge also has a cost. Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with and . The flow circulates through the network, hence the name of the problem.

In a network with gains or generalized network each edge has a gain, a real number (not zero) such that, if the edge has gain g, and an amount x flows into the edge at its tail, then an amount gx flows out at the head.

In a source localization problem, an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating source of disease outbreaks.[8]

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Flow network

View on Grokipedia
from Grokipedia
In graph theory and computer science, a flow network is a directed graph G=(V,E)G = (V, E) with a distinguished source vertex ss and sink vertex tt, where each edge (u,v)∈E(u, v) \in E is assigned a nonnegative capacity c(u,v)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 ff from ss to tt that respects these capacities while maximizing the total flow value. A feasible flow must satisfy three properties: conservation of flow at intermediate vertices (inflow equals outflow), nonnegativity (f(u,v)≥0f(u, v) \geq 0), and capacity constraints (0≤f(u,v)≤c(u,v)0 \leq f(u, v) \leq c(u, v)). The maximum flow problem, which seeks the highest possible flow value from ss to tt, 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 ss- tt cut. 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. Subsequent improvements include the Edmonds-Karp algorithm (1972), a breadth-first search implementation of Ford-Fulkerson achieving polynomial time complexity O(VE2)O(VE^2), and faster methods like Dinic's algorithm (1970) with time complexity O(V2E)O(V^2E) for general graphs. These algorithms underpin efficient solutions to flow problems, with modern variants addressing unit capacities, high precision, or parallel computation for large-scale networks. Flow networks have broad applications across , , and , modeling scenarios involving and . Notable uses include transportation systems for optimizing traffic or shipment routing, bipartite matching for assigning jobs to workers or edges in matchings, in by partitioning pixels based on flow cuts, and network reliability analysis to ensure fault-tolerant connectivity. In , they help solve problems like egalitarian resource distribution or optimization, while extensions to minimum-cost flows incorporate edge costs for scenarios like scheduling.

Core Definitions

Graph Structure

A flow network is defined as a G=(V,E)G = (V, E), consisting of a finite set of vertices VV and a set of directed edges E⊆V×VE \subseteq V \times V, where each edge represents a directed arc from one vertex to another. 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 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. Central to the flow network are two designated terminal vertices: the source s∈Vs \in V and the sink t∈Vt \in V, with s≠ts \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)(u, v) with u,v∈Vu, v \in V and u≠vu \neq v, capturing the one-way nature of connections. 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. Additionally, these networks typically exclude self-loops (arcs of the form (u,u)(u, u)) and parallel arcs between the same pair of vertices, ensuring a simple structure unless explicitly stated otherwise; such assumptions simplify analysis for most applications.

Capacities and Terminals

In a flow network, which builds upon a G=(V,E)G = (V, E), each arc (u,v)∈E(u, v) \in E is assigned a capacity that limits the amount of flow it can carry. The capacity function c:E→R≥0c: E \to \mathbb{R}_{\geq 0} maps each arc to a non-negative , representing the maximum allowable flow along that arc. Capacities are typically fixed at the outset of the problem, providing the static constraints within which flow computations occur. To handle cases where an arc imposes no practical limit, the capacity may be denoted as c(u,v)=∞c(u, v) = \infty, indicating an unbounded arc. 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. The network designates two special vertices: a source s∈Vs \in V as the origin of net outflow and a sink t∈Vt \in V as the destination of net inflow, which together frame the directional flow from start to end. These terminals are fixed prior to any flow assignment, establishing the problem's boundaries.

Flow Fundamentals

Valid Flow Assignment

A valid flow assignment in a flow network is defined by a function f:E→R≥0f: E \to \mathbb{R}_{\geq 0}, which assigns a non-negative real number f(u,v)f(u,v) to each arc (u,v)∈E(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)>0f(u,v) > 0 only if the arc (u,v)(u,v) is present in EE; otherwise, f(u,v)=0f(u,v) = 0 for non-existent arcs. The core property of a valid flow assignment is adherence to capacity constraints on each arc. Specifically, for every arc (u,v)∈E(u,v) \in E, the flow must satisfy 0≤f(u,v)≤c(u,v)0 \leq f(u,v) \leq c(u,v), where c(u,v)c(u,v) is the capacity of the arc, preventing any overload or negative flow. 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)f(u,v) = -f(v,u) for all vertices u,v∈Vu, 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. An example of an invalid flow assignment occurs when f(u,v)>c(u,v)f(u,v) > c(u,v) for any arc (u,v)(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.

Flow Conservation

In a flow network, the conservation property requires that, for every vertex vv that is neither the source ss nor the sink tt, 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 ff, 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 ∑u(u,v)∈Ef(u,v)=∑w(v,w)∈Ef(v,w)\sum_{\substack{u \\ (u,v) \in E}} f(u,v) = \sum_{\substack{w \\ (v,w) \in E}} f(v,w) for all vertices v≠s,tv \neq s, t, where EE 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 ss, the net flow is positive (outflow exceeds inflow), representing the origin of the commodity, while at the sink tt, 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 , , or resources are preserved during , 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 : the flow ff is constructed to satisfy the linear equality constraints above alongside capacity bounds 0≤f(e)≤c(e)0 \leq f(e) \leq c(e) for each edge ee with capacity c(e)c(e). Any solution to this 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 equations, yielding equality for each qualifying vv.

Net Flow and Value

In flow networks, the net flow out of the source vertex ss for a given flow assignment ff captures the total amount of flow originating from ss, accounting for both outgoing and any incoming flows on edges incident to ss. Formally, it is defined as
∣f∣(s)=∑v:(s,v)∈Ef(s,v)−∑u:(u,s)∈Ef(u,s),|f|(s) = \sum_{v : (s,v) \in E} f(s, v) - \sum_{u : (u,s) \in E} f(u, s),
where EE denotes the set of edges in the network. This formulation ensures that the net contribution from the source is precisely measured, even in networks where ss might have incoming edges, though standard constructions often assume no such edges exist to simplify the model. The value of the flow, denoted ∣f∣|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 tt, given by
∣f∣(t)=∑v:(v,t)∈Ef(v,t)−∑u:(t,u)∈Ef(t,u).|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∣=∑vf(s,v)|f| = \sum_{v} f(s, v), directly representing the aggregate outflow from ss. This equivalence underscores the global balance enforced by local conservation, ensuring that the total flow generated at the source ultimately reaches the sink. The centers on finding a valid flow ff that maximizes the flow value ∣f∣|f|, while adhering to edge capacity constraints 0≤f(e)≤c(e)0 \leq f(e) \leq c(e) for all edges ee and the conservation property at intermediate vertices. This optimization objective quantifies the network's overall throughput capacity from source to under the given constraints. Within this framework, an edge (u,v)(u, v) is saturated if f(u,v)=c(u,v)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.

Essential Concepts

Residual Networks

In network flow theory, the residual network associated with a given flow ff in a flow network G=(V,E)G = (V, E) with capacities cc provides a representation of the remaining capacities for potential flow adjustments. For each arc (u,v)∈E(u, v) \in E, the forward residual capacity is defined as cf(u,v)=c(u,v)−f(u,v)c_f(u, v) = c(u, v) - f(u, v), which quantifies the additional flow that can be pushed along that arc without exceeding its original capacity. If f(u,v)>0f(u, v) > 0, a reverse residual arc (v,u)(v, u) is introduced with capacity cf(v,u)=f(u,v)c_f(v, u) = f(u, v), allowing for the reduction or redirection of existing flow to enable further augmentations elsewhere in the network. This bidirectional mechanism ensures that the residual structure captures both untapped potential and opportunities to undo prior flow assignments. The residual graph Gf=(V,Ef)G_f = (V, E_f) is then constructed by including all vertices VV and the set of residual arcs Ef={(u,v)∈V×V∣cf(u,v)>0}E_f = \{(u, v) \in V \times V \mid c_f(u, v) > 0\}, where arcs exist only if their residual capacity is positive. In cases where capacities are unbounded (i.e., c(u,v)=∞c(u, v) = \infty), the corresponding forward residual capacity remains infinite as long as no flow saturates an effectively unlimited arc, preserving the graph's structure for analysis. This formulation, originally introduced in the context of maximal flow computation, enables a dynamic view of the network's state relative to the current flow. As the flow ff is updated—such as through incremental adjustments—the residual graph GfG_f evolves accordingly, with residual capacities recalculated and arcs added or removed based on the new flow values. This dynamic nature makes the residual network a foundational tool for studying flow feasibility and optimization, distinct from the static original graph by emphasizing adjustable rather than fixed constraints. The concept underpins algorithms for maximum flow, as detailed in seminal works on network flows.

Augmenting Paths

In the context of flow networks, an augmenting path is a simple path from the source vertex ss to the sink vertex tt in the residual network GfG_f, where every arc along the path has positive residual capacity cf(u,v)>0c_f(u, v) > 0. This path represents an opportunity to increase the current flow value by redirecting or adding flow without violating capacity constraints. The existence of such paths is fundamental to iteratively improving flow assignments in network optimization. The bottleneck capacity of an augmenting path PP is defined as the minimum residual capacity over all arcs in PP, given by δ=min⁡(u,v)∈Pcf(u,v)\delta = \min_{(u,v) \in P} c_f(u, v). This value δ\delta determines the maximum amount by which the flow can be augmented along PP, limited by the weakest link in the path. To perform augmentation, the flow ff is updated by adding δ\delta to the flow on each forward arc in PP and subtracting δ\delta from the flow on each corresponding reverse arc (if present), which simultaneously updates the residual network GfG_f. This operation preserves flow validity while increasing the net flow value by exactly δ\delta. A key theoretical result states that a flow ff is maximum the residual network GfG_f contains no augmenting path. In such a case, further augmentation is impossible, confirming optimality. For illustration, consider selecting an augmenting path that maximizes the bottleneck capacity, which can lead to fewer augmentations for convergence, though the shortest such path in terms of the number of arcs may also be considered for efficiency in certain contexts.

Flow Decomposition

Flow decomposition provides a method to express a given flow in a network as a of flows along directed paths from the source to the and directed cycles, facilitating and proofs of key properties in flow theory. This technique reveals the underlying path structure of the flow without altering its value or validity, assuming the original flow satisfies conservation and capacity constraints. It is particularly valuable for dissecting complex flows into simpler components for verification or optimization purposes. A fundamental result in network flows is the flow decomposition theorem, which states that any acyclic flow can be decomposed into at most |V|-1 paths and cycles such that the total flow value |f| equals the sum of the values along these components. In general networks, the decomposition includes s-t paths carrying the net flow and possibly cycles representing circulations, with the total number of paths and cycles bounded by |E|, the number of edges; each path in the decomposition carries a positive flow value. This theorem holds for any valid flow and ensures the decomposition preserves the original flow's value and non-negativity. The path decomposition procedure begins by identifying a directed path from the source s to the t consisting solely of edges with positive flow. The minimum flow value along this path is then subtracted from the flow on each edge of the path (often normalized to unit flow for simplicity in cases, though the general step uses the bottleneck minimum), effectively removing that amount of flow while recording it as a separate path flow. This step is repeated on the updated flow until no s-t path with positive flow remains, yielding a set of paths whose flows sum to the original net flow value |f|. The process terminates after at most |E| iterations because each subtraction reduces the number of edges with positive flow by at least one. Cycle elimination addresses circulating components that do not contribute to the net flow value |f|, such as loops where flow circulates without net progress from source to . To eliminate a cycle, a directed cycle with positive flow on all edges is found, and the minimum flow along the cycle is subtracted from each edge in the cycle, reducing or zeroing the circulation without affecting conservation at intermediate nodes or the overall s-t value. These cycles can be iteratively removed until the flow is acyclic, after which path decomposition applies; this step ensures the decomposition focuses on value-contributing components while bounding the total number of cycles by |E|. Flow decomposition plays a crucial role in proving the for maximum flows with capacities, demonstrating that if all edge capacities are , then there exists a maximum flow that is integer-valued on every edge. By decomposing the flow into paths and cycles, each carrying positive amounts bounded by capacities, the shows that the maximum flow value |f| must be , as it equals the sum of path flows up to the min-cut capacity; this avoids fractional flows and guarantees polynomial-time computability via -augmenting algorithms.

Arc Additions and Modifications

In flow networks, adding a new arc (u, v) with capacity c' involves setting the initial flow f(u, v) = 0, which satisfies the capacity constraint f(u, v) ≤ c' and preserves the validity of the existing flow assignment, assuming the original flow was valid. This addition updates the residual network by including a forward residual arc from u to v with capacity c' and a reverse residual arc from v to u with capacity 0. The maximum flow value may increase by up to c', depending on the connectivity from the source to u and from v to the in the residual graph. If the added arc is parallel to an existing arc between the same nodes u and v, the parallel arcs can be combined into a single arc with summed capacity c(u, v) + c' and summed flow f(u, v) + 0, simplifying the network representation without altering the feasible flow set. This merging maintains flow conservation and capacity constraints across the network. Modifying the capacity of an existing arc (u, v) from c to a new value c' requires checking the current flow f(u, v) against c'. If c' > c (capacity increase), the existing flow remains valid since f(u, v) ≤ c ≤ c', and the forward residual capacity increases by c' - c while the reverse residual capacity remains unchanged. This adjustment may raise the upper bound on the maximum flow. Conversely, if c' < c (capacity decrease) and f(u, v) ≤ c', the flow stays valid, but the forward residual capacity decreases by c - c'. However, if f(u, v) > c', the flow becomes invalid, necessitating rebalancing by reducing the excess flow δ = f(u, v) - c' along the arc; this can be achieved by augmenting flow in the residual network along paths or cycles that utilize the reverse arc (v, u) to effectively reroute δ from v back to u, restoring validity while preserving conservation elsewhere. Post-modification, the residual network must be updated accordingly to reflect the new capacities: forward residual r_f(u, v) = c' - f(u, v) and reverse r_f(v, u) = f(u, v). These changes can affect augmenting paths and thus the computable maximum flow, but a valid flow can always be maintained or restored through residual adjustments without recomputing from scratch unless optimality is required.

Variations

Multiple Sources and Sinks

In flow networks with multiple sources and sinks, a standard reduction transforms the problem into an equivalent single-source single-sink form by introducing a super-source node SS and a super-sink node TT. The super-source SS is connected to each original source sis_i via a directed arc with capacity equal to the supply at sis_i, denoted b(si)>0b(s_i) > 0, allowing flow to enter the network only up to the available supply from each source. Similarly, each original sink tjt_j is connected to the super-sink TT via a directed arc with capacity equal to the demand at tjt_j, denoted b(tj)<0b(t_j) < 0, ensuring that flow leaving the sinks does not exceed their demands. The resulting network G′G' retains all original arcs and capacities from the initial graph GG, augmented only by the new arcs from SS to the sources and from the sinks to TT. This construction preserves the maximum flow value, as the maximum flow in G′G' from SS to TT equals the maximum feasible flow in GG that respects the supplies at sources and demands at sinks. Standard maximum flow algorithms, such as Ford-Fulkerson, can then be applied directly to G′G' to compute this value efficiently. For networks with specified supplies and demands, the feasibility of a flow depends on whether the total supply balances the total demand. In a balanced network, where the sum of supplies ∑b(si)\sum b(s_i) equals the sum of absolute demands ∑∣b(tj)∣\sum |b(t_j)|, a feasible maximum flow exists if and only if the computed maximum flow value in G′G' equals this common total, ensuring all supplies are utilized and all demands are met. In an unbalanced network, where total supply exceeds total demand, the maximum flow value equals the total demand, confirming feasibility for satisfying demands; conversely, if total demand exceeds total supply, feasibility requires the maximum flow to equal the total supply, but demands cannot be fully met without additional sources. This reduction extends naturally to transportation problems, where supplies at origins (sources) and demands at destinations (sinks) must be satisfied at minimum cost, modeled as a bipartite flow network with intermediate arcs representing shipping routes and their capacities or costs. By applying the super-source and super-sink construction with arc capacities set to the respective supplies and demands, the transportation problem reduces to a minimum-cost flow problem in the single-source single-sink network G′G', allowing the use of network simplex or other optimization algorithms while preserving feasibility conditions for balanced or unbalanced cases.

Circulation Networks

A circulation in a flow network is defined as a valid flow assignment that satisfies the conservation property at every node, ensuring that the incoming flow equals the outgoing flow with no net accumulation or depletion anywhere in the network. Unlike standard flow problems with specified sources and sinks, circulation networks lack designated terminals, modeling closed systems where flow recirculates indefinitely. Circulations typically incorporate both lower bounds l(u,v)l(u,v) and upper capacities c(u,v)c(u,v) on each directed arc (u,v)(u,v), requiring l(u,v)≤f(u,v)≤c(u,v)l(u,v) \leq f(u,v) \leq c(u,v) for the flow ff to be feasible. The existence of a feasible circulation is governed by Hoffman's circulation theorem, which provides a necessary and sufficient condition: for every subset S⊆VS \subseteq V of nodes, the sum of lower bounds on arcs leaving SS does not exceed the sum of upper bounds on arcs entering SS. To computationally verify feasibility and construct a circulation if it exists, the problem reduces to a maximum flow computation in an auxiliary network. This involves shifting flows by the lower bounds to create residual capacities c′(u,v)=c(u,v)−l(u,v)c'(u,v) = c(u,v) - l(u,v), computing node imbalances b(v)=∑u:(u,v)∈El(u,v)−∑w:(v,w)∈El(v,w)b(v) = \sum_{u: (u,v) \in E} l(u,v) - \sum_{w: (v,w) \in E} l(v,w), and adding a super-source connected to nodes with positive b(v)b(v) and a super-sink to nodes with negative b(v)b(v); a feasible circulation exists if and only if the maximum flow value equals ∑v:b(v)>0b(v)\sum_{v: b(v) > 0} b(v). Any feasible circulation admits a decomposition into edge-disjoint directed cycles, where each cycle carries a positive constant flow value, and the overall circulation is the superposition of these cycle flows; such a decomposition can be obtained using augmenting path methods on the residual network and requires at most ∣E∣|E| cycles. Circulation networks apply to scheduling scenarios without external inputs or outputs, such as closed-loop manufacturing systems where resources cycle through processes or periodic timetabling in transportation networks requiring balanced recurring assignments.

Directed Acyclic Flow Networks

A directed acyclic flow network, or DAG flow network, is a flow network in which the underlying directed graph contains no directed cycles, ensuring that all paths are finite and well-defined. This acyclicity permits a topological ordering of the vertices, where each vertex appears before all vertices reachable from it via directed edges, computable in linear time relative to the number of edges. Such ordering facilitates sequential processing of the network, eliminating concerns about feedback loops in flow propagation. The absence of cycles provides significant computational advantages for solving the . The facilitates efficient implementation of standard algorithms like Edmonds-Karp, achieving O(|V|E^2) , by simplifying residual graph updates and path searches without cycles. In DAG flow networks, flow decomposition yields a representation consisting exclusively of path flows from sources to sinks, without any circulating components, as cycles cannot exist to support such flows. This path-only decomposition aligns naturally with the acyclic structure, often resulting in representations with at most |E| paths, and supports efficient verification of flow conservation and capacity adherence. Layered representations of these networks, constructed by assigning levels via topological depths or longest-path distances, ensure that edges span exactly one level, enabling algorithms to identify unit-length augmenting paths within levels for faster blocking flow computations. These networks are particularly suited to modeling systems with inherent precedence constraints, such as scheduling tasks in or resolving dependencies in computational graphs. In scheduling applications, vertices represent activities, edges denote prerequisites, and flows quantify resource throughput; the integrates flow-based analysis to optimize timelines under capacity limits, computable efficiently due to the DAG topology.

Examples and Applications

Illustrative Example

Consider a simple flow network with four nodes: a source ss, a tt, and two intermediate nodes aa and bb. The directed arcs and their capacities are as follows: s→as \to a with capacity 5, s→bs \to b with capacity 4, a→ta \to t with capacity 3, b→tb \to t with capacity 6, and a→ba \to b with capacity 2. An initial feasible flow can be assigned as f(s→a)=3f(s \to a) = 3, f(a→t)=3f(a \to t) = 3, with all other arcs carrying zero flow. This satisfies the capacity constraints, as 3 ≤ 5 for s→as \to a and 3 ≤ 3 for a→ta \to t, and flow conservation holds at node aa (inflow 3 equals outflow 3) and at bb (inflow 0 equals outflow 0). The current total flow value is 3. The corresponding residual graph includes forward residual capacities (original capacity minus current flow) and backward residual capacities (current flow, allowing potential flow reduction). Thus, the residuals are: s→as \to a: 2 forward, a→sa \to s: 3 backward; a→ta \to t: 0 forward, t→at \to a: 3 backward; s→bs \to b: 4 forward; b→tb \to t: 6 forward; a→ba \to b: 2 forward. An augmenting path exists from ss to tt, such as s→b→ts \to b \to t, with bottleneck residual capacity min⁡(4,6)=4\min(4, 6) = 4. Augmenting along this path increases the flow by 4, updating f(s→b)=4f(s \to b) = 4 and f(b→t)=4f(b \to t) = 4, for a new total flow of 7. In the updated residual graph, another augmenting path exists: s→a→b→ts \to a \to b \to t, with bottleneck residual capacity min⁡(2,2,2)=2\min(2, 2, 2) = 2. Augmenting along this path increases the flow by 2, updating f(s→a)=5f(s \to a) = 5, f(a→b)=2f(a \to b) = 2, and f(b→t)=6f(b \to t) = 6, for a total flow of 9. No further augmenting paths remain, confirming this is the maximum flow. This maximum flow of 9 can be decomposed into path flows: the path s→a→ts \to a \to t carrying 3 units, the path s→a→b→ts \to a \to b \to t carrying 2 units, and the path s→b→ts \to b \to t carrying 4 units, illustrating how the total flow arises from paths in the network.

Practical Applications

Flow networks find extensive application in transportation systems, where they model the movement of goods or across or rail infrastructures. Edges represent routes with capacities corresponding to limits such as vehicle throughput or bandwidth, while sources simulate origins like distribution centers and sinks denote destinations such as ports or markets. This formulation allows optimization of flows to minimize congestion and maximize efficiency in supply chains. In assignment and matching scenarios, flow networks underpin bipartite matching problems, where the maximum flow equates to the largest possible pairing between two sets, such as workers and tasks. This approach leverages , which guarantees a under certain neighborhood conditions, facilitating real-world uses like job scheduling or in . For instance, the theorem ensures feasible assignments when each subset of jobs has sufficient compatible machines. Image segmentation employs min-cut techniques from flow networks to delineate regions in visual data, treating pixels as nodes and similarities between adjacent pixels as edge capacities. By partitioning the graph into source-connected (foreground) and sink-connected (background) components, the minimum cut identifies optimal boundaries that minimize segmentation energy, enhancing tasks like . The elimination problem uses flow networks to assess whether a can still mathematically contend for a league title given current standings and remaining games. Nodes represent teams and games, with capacities encoding wins and schedules; the maximum flow value determines if reallocating remaining games allows the team to surpass leaders, providing a precise feasibility check for . Network reliability analysis utilizes the maximum flow value as a measure of connectivity, quantifying the capacity (total capacity removal) needed to isolate a source from a ; in unit-capacity networks, this equals the minimum number of edge removals required, reflecting robustness against failures in communication or power grids. This metric guides improvements by evaluating under capacity constraints.

Problem Classifications

Maximum Flow Problems

The maximum flow problem in a flow network G=(V,E)G = (V, E) with source s∈Vs \in V, sink t∈Vt \in V, and nonnegative capacity function c:E→R≥0c: E \to \mathbb{R}_{\geq 0} is to find a valid flow f:E→R≥0f: E \to \mathbb{R}_{\geq 0} that maximizes the flow value ∣f∣=fout(s)=fin(t)|f| = f_{\text{out}}(s) = f_{\text{in}}(t), subject to the capacity constraints 0≤f(e)≤c(e)0 \leq f(e) \leq c(e) for all e∈Ee \in E and the flow conservation constraints ∑e∈Ein(v)f(e)=∑e∈Eout(v)f(e)\sum_{e \in E_{\text{in}}(v)} f(e) = \sum_{e \in E_{\text{out}}(v)} f(e) for all v∈V∖{s,t}v \in V \setminus \{s, t\}. A fundamental result connecting the maximum flow to graph structure is the , which asserts that the value of the maximum flow equals the capacity of the minimum s-t cut in the network. An s-t cut is defined as a partition of the vertex set VV into two subsets (S,T)(S, T) such that s∈Ss \in S and t∈Tt \in T, with the capacity of the cut given by the sum ∑(u,v)∈E:u∈S,v∈Tc(u,v)\sum_{(u,v) \in E: u \in S, v \in T} c(u,v). The proof of the proceeds in two parts. First, for any valid flow ff, the flow value ∣f∣|f| is at most the capacity of any s-t cut, since the net flow out of SS cannot exceed the total capacity crossing from SS to TT. Second, if a flow ff is not maximum, then in the residual graph GfG_f (where residual capacities allow backward flow along saturated edges), there exists a path from ss to tt that can augment the flow, increasing ∣f∣|f| until no such path remains; at that point, the set of vertices reachable from ss in GfG_f defines a minimum-capacity s-t cut whose capacity equals ∣f∣|f|. An important property of the maximum flow problem is the integrality , which states that if all edge capacities c(e)c(e) are s, then there exists a maximum flow ff where f(e)f(e) is an for every edge e∈Ee \in E. This follows from the fact that augmenting along paths with integer residual capacities preserves integrality, ensuring an solution at optimality.

Minimum Cut Problems

In a flow network G=(V,E)G = (V, E) with source ss and sink tt, an ss-tt cut is a partition of the vertex set VV into two disjoint subsets SS and T=V∖ST = V \setminus S such that s∈Ss \in S and t∈Tt \in T. The capacity of this cut, denoted c(S,T)c(S, T), is the sum of the capacities of all edges directed from SS to TT: c(S,T)=∑u∈S,v∈Tc(u,v),c(S, T) = \sum_{u \in S, v \in T} c(u, v), where c(u,v)c(u, v) is the capacity of edge (u,v)(u, v). This capacity represents the total throughput limit imposed by the edges crossing the partition. The minimum ss-tt cut is the partition (S,T)(S, T) that minimizes c(S,T)c(S, T) over all possible ss-tt cuts. By the , the capacity of the minimum ss-tt cut equals the value of the maximum flow from ss to tt. This duality, established in seminal work on network flows, underscores that the minimum cut capacity defines the fundamental bottleneck limiting flow through the network. One minimum ss-tt cut can be identified using the residual graph GfG_f after computing a maximum flow ff: let SS be the set of vertices reachable from ss in GfG_f, with T=V∖ST = V \setminus S. This partition (S,T)(S, T) has capacity equal to the maximum flow value, as all edges from SS to TT are saturated under ff and no residual capacity exists from TT to SS. This construction yields the closest to the source (the source-side minimum cut), which is the smallest such SS containing ss. Flow networks may admit multiple minimum ss-tt cuts, all sharing the same minimum capacity. The source-side variant is as defined above, while the sink-side variant (closest to the sink) is obtained by taking SS as the complement of the vertices from which tt is reachable in GfG_f (or equivalently, vertices reachable from tt in the of GfG_f). All minimum cuts lie between these source-side and sink-side partitions, forming a lattice closed under and union. The existence of multiple cuts occurs when the residual graph after maximum flow has vertices neither reachable from ss nor reaching tt. Minimum cuts have key applications in bottleneck analysis, where they pinpoint the weakest set of edges constraining overall —for instance, in transportation or communication systems, revealing critical links whose reinforcement would increase maximum flow capacity. The extends the basic flow network by introducing on edges and seeking a feasible flow of a prescribed total value bb that minimizes the aggregate . Formally, it optimizes min⁡∑(u,v)∈Ef(u,v)⋅c(u,v)\min \sum_{(u,v) \in E} f(u,v) \cdot c(u,v), where c(u,v)c(u,v) denotes the cost per unit flow on edge (u,v)(u,v), subject to capacity constraints 0≤f(u,v)≤κ(u,v)0 \leq f(u,v) \leq \kappa(u,v) for all edges, flow conservation at non-source/ nodes, and the net flow out of the source equaling bb. This variant captures scenarios where efficiency depends not just on throughput but on economic factors, and it generalizes problems like the transportation and assignment tasks. Parametric flow networks generalize capacities as functions of one or more parameters, such as κ(u,v)(λ)\kappa(u,v)(\lambda) where λ\lambda varies continuously, enabling the study of how maximum flow values change with perturbations like resource scaling or uncertainty. These models are useful for , where the goal is to compute the flow or cut values across a range of λ\lambda efficiently, often revealing breakpoints where the optimal structure shifts. Seminal algorithms for parametric maximum flow leverage repeated invocations of non-parametric solvers while exploiting monotonicity in capacity functions to achieve polynomial-time solutions for concave or linear cases. In multi-commodity flow problems, multiple distinct commodities—each defined by its own source-sink pair and —share the network's edge capacities, requiring simultaneous that respects the aggregate load on each edge. The optimization typically maximizes the minimum satisfaction across commodities or the total routed , contrasting with single-commodity flows by introducing inter-commodity interference. This formulation, rooted in early studies of communication and systems, often admits relaxation to linear programs for , though integrality gaps persist in dense networks. Unspltittable flow imposes the constraint that each commodity's entire must traverse a single path, prohibiting fractional splitting across routes, which introduces non-convexity and even for simple topologies. Unlike splittable variants, this requires integer decisions on path selection, leading to objectives like minimizing congestion or maximizing throughput under path-integrality. Approximation algorithms achieve constant-factor guarantees relative to the splittable optimum, with performance degrading in high-demand scenarios, as established in foundational results for single-source cases. The successive shortest path framework underpins solutions to many flow variants, including minimum and multi-commodity problems, by iteratively finding and augmenting along shortest paths in the residual graph using reduced costs to maintain optimality. Starting from a zero-flow or initial feasible solution, it builds the flow incrementally until demands are met, with each iteration resolving a shortest path subproblem via Dijkstra or Bellman-Ford adaptations. This capacity-scaling approach extends naturally to capacitated and circulation variants, offering a unified method for both maximum throughput and cost-minimization objectives.

References

  1. https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/7c2927794e61bd70c14c07728fa54375_MIT6_046JS12_lec13.pdf
  2. https://www2.cs.arizona.edu/classes/cs445/fall15/Network-Flow.pdf
  3. https://www.cs.yale.edu/homes/lans/readings/routing/ford-max_flow-1956.pdf
  4. https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/07NetworkFlowI.pdf
  5. https://www.cs.cornell.edu/~eva/Network.Flow.Algorithms.pdf
  6. http://www.cs.ucf.edu/~dmarino/progcontests/modules/netflow2/NetFlow-Apps.pdf
  7. https://courses.cs.vt.edu/~cs4104/murali/Fall09/lectures/lecture-22-network-flow-applications.pdf
  8. https://www.cs.williams.edu/~shikha/teaching/spring20/cs256/lectures/Lecture20.pdf
  9. https://courses.grainger.illinois.edu/cs473/sp2011/lectures/18_notes.pdf
  10. https://cse.buffalo.edu/~hungngo/classes/2007/Network%20Coding/notes/flow-intro.pdf
  11. https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764
  12. https://www.cs.cornell.edu/courses/cs6820/2019fa/handouts/maxflow-mincut.pdf
  13. https://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec4.pdf
  14. http://www.cse.buffalo.edu/~hungngo/classes/2004/594/notes/Flow-intro.pdf
  15. https://www.cs.cmu.edu/~15451-f23/lectures/lecture12-flow-i.pdf
  16. https://people.engr.tamu.edu/j-chen3/courses/629/2022/Lectures/notes5.pdf
  17. https://www.cs.cornell.edu/courses/cs6820/2017fa/handouts/flows.pdf
  18. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/netflow.pdf
  19. https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2005/8346e77d563c80b0ae714a21bc9a4541_max_flow_dff.pdf
  20. https://jeffe.cs.illinois.edu/teaching/algorithms/book/10-maxflow.pdf
  21. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s21/www/notes/lec11.pdf
  22. https://dspace.mit.edu/bitstream/handle/1721.1/49424/networkflows00ahuj.pdf
  23. https://cacm.acm.org/research/efficient-maximum-flow-algorithms/
  24. https://books.google.com/books/about/Network_Flows.html?id=WnZRAAAAMAAJ
  25. https://personal.utdallas.edu/~metin/Or6201/network.pdf
  26. https://pages.cs.wisc.edu/~dieter/ICPC/12-13/netflow.html
  27. https://web.mit.edu/15.053/www/AMP-Chapter-08.pdf
  28. https://www.networkflowalgs.com/book.pdf
  29. https://www.tau.ac.il/~hassin/hoffman.pdf
  30. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
  31. https://www.cambridge.org/core/books/network-flow-algorithms/816B5B0CBE5471289D22D40D5F8F276A
  32. https://works.swarthmore.edu/context/fac-math-stat/article/1110/viewcontent/directed_acyclic_graphs.pdf
  33. http://theory.stanford.edu/~trevisan/cs261/lecture14.pdf
  34. https://dl.acm.org/doi/10.1109/tpami.2004.60
  35. https://www.cs.princeton.edu/courses/archive/spr03/cos226/assignments/baseball.html
  36. https://www.columbia.edu/~cs2035/courses/ieor6614.S16/mcf.pdf
  37. https://jeffe.cs.illinois.edu/teaching/algorithms/notes/G-mincostflow.pdf
  38. https://epubs.siam.org/doi/10.1137/0218003
  39. https://www.utdallas.edu/~chandra/documents/networks/net7.pdf
  40. http://snap.stanford.edu/class/cs224w-readings/leighton99mincut.pdf
  41. https://link.springer.com/article/10.1007/s004930050043
  42. https://ieeexplore.ieee.org/document/548465
  43. https://www.columbia.edu/~cs2035/courses/ieor6614.S16/mcf-sp.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.