Information about Flow Network

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge may not 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, except when it is a source, which has more outgoing flow, or sink, which has more incoming flow. A network can be used to model 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.

Definition

Suppose is a finite directed graph in which every edge has a non-negative, real-valued capacity . If , we assume that . We distinguish two vertices: a source and a sink . A flow network is a real function with the following three properties for all nodes and :

Capacity constraints:	. The flow along an edge cannot exceed its capacity.
Skew symmetry:	. The net flow from to must be the opposite of the net flow from to (see example).
Flow conservation:	, unless or . The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.

Notice that is the net flow from to . If the graph represents a physical network, and if there is a real flow of for example 4 units from to , and a real flow of 3 units from to , we have and .

The residual capacity of an edge is . This defines a residual network denoted , giving the amount of available capacity. See that there can be an edge from to in the residual network, even though there is no edge from to in the original network. Since flows in opposite directions cancel out, decreasing the flow from to is the same as increasing the flow from to . An augmenting path is a path in the residual network, where , , and . A network is at maximum flow if and only if there is no augmenting path in the residual network.

Example

A flow network showing flow and capacity.

To the right you see a flow network with source labeled , sink , and four additional nodes. The flow and capacity is denoted . Notice how the network upholds skew symmetry, capacity constraints and flow conservation. The total amount of flow from to is 5, which can be easily seen from the fact that the total outgoing flow from is 5, which is also the incoming flow to . 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 . This flow is not a maximum flow. There is available capacity along the paths , and , which are then the augmenting paths. The residual capacity of the first path is . Notice that augmenting path 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 to , and a flow of 1 from to , but we only maintain the net flow.

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.

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 has a given cost , and the cost of sending the flow across the edge is . 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 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.

References

• Ravindra K. Ahuja, Thomas L. Magnanti, and 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 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. 

See also

• Max-flow min-cut theorem
• Ford-Fulkerson algorithm

External links

• Maximum Flow Problem
• Maximum Flow

graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.

In mathematics, the real numbers may be described informally as numbers that can be given by an infinite decimal representation, such as 2.4871773339…. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as π and
..... Click the link for more information.

function expresses dependence between two quantities, one of which is given (the independent variable, argument of the function, or its "input") and the other produced (the dependent variable, value of the function, or "output").
..... Click the link for more information.

maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum ^[1]. Sometimes it is defined as finding the value of such a flow.
..... Click the link for more information.

Electricity distribution is the penultimate stage in the delivery (before retail) of electricity to end users. It is generally considered to include medium-voltage (less than 50 kV) power lines, electrical substations and pole-mounted transformers, low-voltage (less than 1000 V)
..... Click the link for more information.

Béla Bollobás (born August 3, 1943 in Budapest, Hungary) is a leading Hungarian mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics and graph theory.
..... Click the link for more information.

Not to be confused with Kerckhoffs' principle.

Kirchhoff's circuit laws are a pair of laws that deal with the conservation of charge and energy in electrical circuits, and were first described in 1845 by Gustav Kirchhoff.
..... Click the link for more information.

Ecology (also known as Oekologie, Okology, or Oekology^[1],from Greek: οίκος, oikos, "household"; and λόγος, logos
..... Click the link for more information.

Food chains, food webs and/or food networks describe the feeding relationships between species in an ecological community. They graphically represent the transfer of material and energy from one species to another within an ecosystem.
..... Click the link for more information.

Robert E. Ulanowicz (b. September 17, 1943 in Baltimore) is a theoretical ecologist who is best known for his search for a "unified theory of ecology". He is Professor of Theoretical Ecology at the University of Maryland's Chesapeake Biological Laboratory.
..... Click the link for more information.

Information theory is a branch of applied mathematics and engineering involving the quantification of information to find fundamental limits on compressing and reliably communicating data.
..... Click the link for more information.

Thermodynamics (from the Greek θερμη, therme, meaning "heat" and δυναμις, dynamis, meaning "power") is a branch of physics that studies the effects of changes in temperature, pressure, and volume on
..... Click the link for more information.

maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum ^[1]. Sometimes it is defined as finding the value of such a flow.
..... Click the link for more information.

matching or edge independent set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.

Definition

Given a graph G = (V,E), a matching M in
..... Click the link for more information.

The assignment problem is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics. It consists of finding a maximum weight matching in a weighted bipartite graph.
..... Click the link for more information.

In mathematics and economics, transportation theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781^[1].
..... Click the link for more information.

The multi-commodity flow problem is a network flow problem with multiple commodities (or goods) flowing through the network, with different source and sink nodes.

Definition

Given a flow network , where edge has capacity .
..... Click the link for more information.

The minimum cost flow problem is finding the cheapest possible way of sending a certain amount of flow through a flow network.

Definition

Given a flow network with source and sink , where edge has capacity , flow , and the cost of sending this flow is .
..... Click the link for more information.

The circulation problem and its variants is a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes).
..... Click the link for more information.

A gain graph is a graph whose edges are labelled invertibly, or orientably, by elements of a group G. This means that, if an edge e in one direction has label g (a group element), then in the other direction it has label g
..... Click the link for more information.

Thomas L. Magnanti
Born

Residence United States
Citizenship American
Field Operations Research, Management
Institutions MIT
Alma mater Stanford University (PhD)
..... Click the link for more information.

Béla Bollobás (born August 3, 1943 in Budapest, Hungary) is a leading Hungarian mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics and graph theory.
..... Click the link for more information.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College.
..... Click the link for more information.

Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.
..... Click the link for more information.

..... Click the link for more information.

Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in
..... Click the link for more information.

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities.
..... Click the link for more information.

The max-flow min-cut theorem is a statement in optimization theory about maximum flows in flow networks. It derives from Menger's theorem. It states that:

The maximum amount of flow is equal to the capacity of a minimal cut.

..... Click the link for more information.