Flow network

From Wikipedia, the free encyclopedia

In graph theory, a flow network is an assignment of flow to the edges of a directed graph where each edge has a capacity, such that the amount of flow along an edge does not exceed its capacity. (A directed graph with edge capacities is called a network.) A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to simulate traffic in a road system, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes.

1 Definition
2 Example
3 Applications
4 Generalisations and specialisations
5 References
6 See also
7 External links

[edit] Definition

Suppose $G (V, E)$ is a finite directed graph in which every edge $(u,v) \in E$ has a non-negative, real-valued capacity $c (u, v)$ . If $(u, v) \not \in E$ , we assume that $c (u, v) = 0$ . We distinguish two vertices: a source $s$ and a sink $t$ . A flow network is a real function $f:V \times V \rightarrow \mathbb{R}$ with the following three properties for all nodes $u$ and $v$ :

Capacity constraints:	$\ f(u,v) \le c(u,v)$ . The flow along an edge cannot exceed its capacity.
Skew symmetry:	$\ f(u,v) = - f(v,u)$ . The net flow from $u$ to $v$ must be the opposite of the net flow from $v$ to $u$ (see example).
Flow conservation:	$\ \sum_{w \in V} f(u,w) = 0$ , unless $u = s$ or $u = t$ . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

Notice that $f (u, v)$ is the net flow from $u$ to $v$ . If the graph represents a physical network, and if there is a real flow of for example 4 units from $u$ to $v$ , and a real flow of 3 units from $v$ to $u$ , we have $f (u, v) = 1$ and $f (v, u) = - 1$ .

The residual capacity of an edge is $c f (u, v) = c (u, v) - f (u, v)$ . This defines a residual network denoted $G f (V, E f)$ , giving the amount of available capacity. See that there can be an edge from $u$ to $v$ in the residual network, even though there is no edge 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$ . An augmenting path is a path $(u_1,u_2,\dots,u_k)$ , where $u 1 = s$ , $u k = t$ , and $c f (u i, u i + 1) > 0$ , which means it is possible to send more flow along this path.

[edit] Example

A flow network showing flow and capacity.

To the right you see a flow network with source labeled $s$ , sink $t$ , and four additional nodes. The flow and capacity is denoted $f / c$ . Notice how the network upholds skew symmetry, capacity constraints and flow conservation. 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$ . We know that no flow appears or disappears in any of the other nodes.

Residual network for the above flow network, showing residual capacities.

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 $(d, c)$ . This flow is not a maximal flow. There is available capacity along the paths $(s, a, c, t)$ , $(s, a, b, d, t)$ and $(s, a, b, d, c, t)$ , which are then the augmenting paths. The residual capacity of the first path is $min(c (s, a) - f (s, a), c (a, c) - f (a, c), c (c, t) - f (c, t)) = min(5 - 3,3 - 2,2 - 1) = min(2,1,1) = 1$ . Notice that augmenting path $(s, a, b, d, c, t)$ does not exist in the original network, but you can send flow along it, and still get a legal flow.

If this is a real network, there might actually be a flow of 2 from $a$ to $b$ , and a flow of 1 from $b$ to $a$ , but we only maintain the net flow.

[edit] Applications

Picture a series of water pipes, fitting into a network. Each pipe is of a certain width, 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 build up 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. Bollobás characterizes this constraint in terms of Kirchhoff's current law, while later authors (ie: Chartrand) mention its generalization to some conservation equation.

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.

[edit] Generalisations and specialisations

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.

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 $u, v$ has a given cost $k (u, v)$ , and the cost of sending the flow $f (u, v)$ across the edge is $f(u,v) \cdot k(u,v)$ . The object 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 $l (u, v)$ on the edges, in addition to the upper bound $c (u, v)$ . 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 $l (t, s)$ and $c (t, s)$ . 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.

[edit] References

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 ISBN 0-521-24659-8.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein [1990] (2001). "26", Introduction to Algorithms, 2nd edition, MIT Press and McGraw-Hill, 696-697. ISBN 0-262-03293-7.