Ingraph theory, aflow network (also known as atransportation network) is adirected graph where each edge has acapacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often inoperations research, a directed graph is called anetwork, the vertices are callednodes and the edges are calledarcs. 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 asource, which has only outgoing flow, orsink, 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 thematching problem.

Anetwork is a directed graphG = (V,E) with a non-negativecapacityfunctionc 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 ofE. Additionally, if(v,u) ∉E then we may add(v,u) toE and then set thec(v,u) = 0.

If two nodes inG are distinguished – one as the sources and the other as the sinkt – then(G,c,s,t) is called aflow network.^[1]

Flow functions model the net flow of units between pairs of nodes, and are useful when asking questions such aswhat 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.

Theexcess functionx_f :V → ℝ represents the net flow entering a given nodeu (i.e. the sum of the flows enteringu) and is defined by$${\displaystyle x_f(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).}$$A nodeu is said to beactive ifx_f (u) > 0 (i.e. the nodeu consumes flow),deficient ifx_f (u) < 0 (i.e. the nodeu produces flow), orconserving ifx_f (u) = 0. In flow networks, the sources is deficient, and the sinkt is active.Pseudo-flows, feasible flows, and pre-flows are all examples of flow functions.

Apseudo-flow is a functionf of each edge in the network that satisfies the following two constraints for all nodesu andv:

• Skew symmetry constraint: The flow on an arc fromu tov is equivalent to the negation of the flow on the arc fromv tou, 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).

Apre-flow is a pseudo-flow that, for allv ∈V \{s}, satisfies the additional constraint:

• Non-deficient flows: The net flowentering the nodev is non-negative, except for the source, which "produces" flow. That is:x_f (v) ≥ 0 for allv ∈V \{s}.

Afeasible flow, or just aflow, is a pseudo-flow that, for allv ∈V \{s,t}, satisfies the additional constraint:

• Flow conservation constraint: The total net flow entering a nodev is zero for all nodes in the network except the sources and the sinkt, that is:x_f (v) = 0 for allv ∈V \{s,t}. In other words, for all nodes in the network except the sources and the sinkt, the total sum of the incoming flow of a node is equal to its outgoing flow (i.e.${\displaystyle \sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)}$, for each vertexv ∈V \{s,t}).

Thevalue|f| of a feasible flowf for a network, is the net flow into the sinkt of the flow network, that is:|f| =x_f (t). Note, the flow value in a network is also equal to the total outgoing flow of sources, that is:|f| = −x_f (s). Also, if we defineA as a set of nodes inG such thats ∈A andt ∉A, the flow value is equal to the total net flow going out of A (i.e.|f| =f ^out(A) −f ⁱⁿ(A)).^[2] The flow value in a network is the total amount of flow froms tot.

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.

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2023) (Learn how and when to remove this message)

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 nodesu andv, having two arcs fromu tov with capacitiesc₁(u,v) andc₂(u,v) respectively is equivalent to considering only a single arc fromu tov with a capacity equal toc₁(u,v)+c₂(u,v).
• Given any two nodesu andv, having two arcs fromu tov with pseudo-flowsf₁(u,v) andf₂(u,v) respectively is equivalent to considering only a single arc fromu tov with a pseudo-flow equal tof₁(u,v)+f₂(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]}

Theresidual capacity of an arce with respect to a pseudo-flowf is denotedc_f, and it is the difference between the arc's capacity and its flow. That is,c_f (e) =c(e) −f(e). From this we can construct aresidual network, denotedG_f (V,E_f), with a capacity functionc_f which models the amount ofavailable capacity on the set of arcs inG = (V,E). More specifically, capacity functionc_f of each arc(u,v) in the residual network represents the amount of flow which can be transferred fromu tov given the current state of the flow within the network.

This concept is used inFord–Fulkerson algorithm which computes themaximum flow in a flow network.

Note that there can be an unsaturated path (a path with available capacity) fromu tov in the residual network, even though there is no such path fromu tov in the original network.^{[citation needed]} Since flows in opposite directions cancel out,decreasing the flow fromv tou is the same asincreasing the flow fromu tov.

Anaugmenting path is a path(u₁,u₂, ...,u_k) in the residual network, whereu₁ =s,u_k =t, andfor allu_i,u_{i + 1} (c_f (u_i,u_{i + 1}) > 0) (1 ≤ i < k). More simply, an augmenting path is an available flow path from the source to the sink. A network is atmaximum flow if and only if there is no augmenting path in the residual networkG_f.

Thebottleneck 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 flowf of each arc in this augmenting path to equal the capacityc 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.

Sometimes, when modeling a network with more than one source, asupersource 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 asupersink.^[5]

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2023) (Learn how and when to remove this message)

In Figure 1 you see a flow network with source labeleds, sinkt, and four additional nodes. The flow and capacity is denoted${\displaystyle f/c}$. Notice how the network upholds the capacity constraint and flow conservation constraint. The total amount of flow froms tot is 5, which can be easily seen from the fact that the total outgoing flow froms is 5, which is also the incoming flow tot. By the skew symmetry constraint, fromc toa is -2 because the flow froma toc is 2.

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${\displaystyle (d,c)}$. This network is not atmaximum flow. There is available capacity along the paths${\displaystyle (s,a,c,t)}$,${\displaystyle (s,a,b,d,t)}$ and${\displaystyle (s,a,b,d,c,t)}$, which are then the augmenting paths.

The bottleneck of the${\displaystyle (s,a,c,t)}$ path is equal to${\displaystyle min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))}$${\displaystyle =min(c_f(s,a),c_f(a,c),c_f(c,t))}$${\displaystyle =min(5-3,3-2,2-1)}$${\displaystyle =min(2,1,1)=1}$.

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(June 2023) (Learn how and when to remove this message)

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 overelectrical 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 toKirchhoff's current law.

Flow networks also find applications inecology: flow networks arise naturally when considering the flow of nutrients and energy between different organisms in afood 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 byRobert Ulanowicz and others, involves using concepts frominformation theory andthermodynamics to study the evolution of these networks over time.

The simplest and most common problem using flow networks is to find what is called themaximum 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 asbipartite matching, theassignment problem and thetransportation problem. Maximum flow problems can be solved inpolynomial time with various algorithms (see table). Themax-flow min-cut theorem states that finding a maximal network flow is equivalent to finding acut 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 (withn nodes andm 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	${\displaystyle O(m^{1+o(1)})}$

In amulti-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 thesame transportation network.

In aminimum cost flow problem, each edge${\displaystyle u,v}$ has a given cost${\displaystyle k(u,v)}$, and the cost of sending the flow${\displaystyle f(u,v)}$ across the edge is${\displaystyle f(u,v)\cdot k(u,v)}$. The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In acirculation problem, you have a lower bound${\displaystyle \ell (u,v)}$ on the edges, in addition to the upper bound${\displaystyle c(u,v)}$. Each edge also has a cost. Often, flow conservation holds forall 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${\displaystyle \ell (t,s)}$ and${\displaystyle c(t,s)}$. The flowcirculates through the network, hence the name of the problem.

In anetwork with gains orgeneralized network each edge has again, a real number (not zero) such that, if the edge has gaing, and an amountx flows into the edge at its tail, then an amountgx flows out at the head.

In asource 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]

• Braess's paradox
• Centrality
• Ford–Fulkerson algorithm
• Edmonds-Karp algorithm
• Dinic's algorithm
• Traffic flow (computer networking)
• Flow graph (disambiguation)
• Max-flow min-cut theorem
• Oriented matroid
• Shortest path problem
• Nowhere-zero flow
• Active flow network

• George T. Heineman; Gary Pollice; Stanley Selkow (2008). "Chapter 8:Network Flow Algorithms".Algorithms in a Nutshell.Oreilly Media. pp. 226–250.ISBN 978-0-596-51624-6.
• Ravindra K. Ahuja;Thomas L. Magnanti;James B. Orlin (1993).Network Flows: Theory, Algorithms and Applications. Prentice Hall.ISBN 0-13-617549-X.
• Bollobás, Béla (1979).Graph Theory: An Introductory Course. Heidelberg: Springer-Verlag.ISBN 3-540-90399-2.
• Chartrand, Gary;Oellermann, Ortrud R. (1993).Applied and Algorithmic Graph Theory. New York: McGraw-Hill.ISBN 0-07-557101-3.
• Even, Shimon (1979).Graph Algorithms. Rockville, Maryland: Computer Science Press.ISBN 0-914894-21-8.
• Gibbons, Alan (1985).Algorithmic Graph Theory. Cambridge: Cambridge University Press.ISBN 0-521-28881-9.
• Thomas H. Cormen;Charles E. Leiserson;Ronald L. Rivest;Clifford Stein (2001) [1990]. "26".Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 696–697.ISBN 0-262-03293-7.

Wikimedia Commons has media related toFlow networks.

• Maximum Flow Problem
• Real graph instances
• Lemon C++ library with several maximum flow and minimum cost circulation algorithms
• QuickGraphArchived 2018-01-21 at theWayback Machine, graph data structures and algorithms for .Net

• Network flow problem

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from June 2023
• All articles needing additional references
• All articles with unsourced statements
• Articles with unsourced statements from February 2023
• Articles with unsourced statements from January 2023
• Commons category link from Wikidata
• Webarchive template wayback links