Flow network
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.
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.
In flow networks, the source s is deficient, and the sink t is active.
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.
[citation needed] 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.
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.
The bottleneck is the minimum residual capacity of all the edges in a given augmenting path.
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.
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, a supersource is introduced to the graph.
[5] In Figure 1 you see a flow network with source labeled s, sink t, and four additional nodes.
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.
Intuitively, the total flow of a network is the rate at which water comes out of the outlet.
This conservation constraint is equivalent to Kirchhoff's current law.
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.
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.
Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva 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
The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.
Often, flow conservation holds for all nodes in a circulation problem, and there is a connection from the sink back to the source.
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.
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.
