![]() | ||
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 network can be used to model traffic in a road system, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.
Contents
Definition
A network is a graph G = (V, E), together with a non-negative function c: V × V → ℝ∞, called the capacity function. Without loss of generality, it is assumed that if (u, v) ∈ E then (v, u) is also a member of E, since if (v, u) ∉ E then (v, u) may be added to E and then setting c(v, u) = 0.
If two nodes in G are distinguished, a source s and a sink t, then (G, c, s, t) is called a flow network.
Flows
There are various notions of a flow function that can be defined in a flow graph. 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 simplest example of a flow function is known as a pseudo-flow.
A pseudo-flow is a function f : V × V → ℝ that satisfies the following two constraints for all nodes u and v:
Given a pseudo-flow f in a flow network, it is often useful to consider the net flow entering a given node v, that is, the sum of the flows entering v. The excess function xf : V → ℝ is defined by xf (u) = ∑v ∈ V f (v, u). A node u is said to be active if xf (u) > 0, deficient if xf (u) < 0 or conserving if xf (u) = 0.
These final definitions lead to two strengthenings of the definition of a pseudo-flow:
A pre-flow is a pseudo-flow that, for all v ∈ V {s}, satisfies the additional constraint:
The value of a feasible flow f, denoted | f |, is the net flow into the sink t of the flow network. That is, | f | = xf (t).
Intuition
In the context of flow analysis, there is only an interest in considering how units are transferred between nodes in a holistic sense. Put another way, it is not necessary to distinguish multiple arcs between a pair of nodes:
For this reason, the capacity function c: V × V → ℝ∞, which does not allow for multiple arcs starting and ending at the same nodes, is sufficient for flow analysis. Similarly, it is enough to impose the skew symmetry constraint on flow functions to ensure that flow between two vertices is encoded by a single number (to indicate magnitude), and a sign (to indicate direction) — by knowing the flow between u and v you implicitly, via skew symmetry, know the flow between v and u. These simplifications of the model aren't always immediately intuitive, but they are convenient when it comes time to analysing flows.
The capacity constraint simply ensures that a flow on any one arc within the network cannot exceed the capacity of that arc.
Residuals
The residual capacity of an arc with respect to a pseudo-flow f, denoted cf, 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), which models the amount of available capacity on the set of arcs in G = (V, E). More formally, given a flow network G, the residual network Gf has the node set V, arc set Ef = {e ∈ E : cf (e) > 0} and capacity function cf.
This concept is used in Ford–Fulkerson algorithm which computes the maximum flow in a flow network.
Note that there can be a path from u to v in the residual network, even though there is no path from u to v in the original network. 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
An augmenting path is a path (u1, u2, ..., uk) in the residual network, where u1 = s, uk = t, and cf (ui, ui + 1) > 0. A network is at maximum flow if and only if there is no augmenting path in the residual network Gf.
Multiple sources and/or sinks
Sometimes one needs to model a network with more than one source, a supersource is introduced to the graph. 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.
Example
To the left you see a flow network with source labeled s, sink t, and four additional nodes. The flow and capacity is denoted
Below you see the residual network for the given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero, for example for the edge
Applications
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 organizations 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.
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 efficiently with the relabel-to-front algorithm. 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.
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
In a circulation problem, you have a lower bound
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 village of disease outbreaks.