Namespaces
Variants
Actions

Difference between revisions of "Flow in a network"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (+ category)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
f0406601.png
 +
$#A+1 = 43 n = 0
 +
$#C+1 = 43 : ~/encyclopedia/old_files/data/F040/F.0400660 Flow in a network
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
A function which assigns certain numbers to the arcs of a given [[Network graph|network graph]] (directed graph). Each number is interpreted as the intensity of the flow along the given arc. Flows in a network form a convenient model in the studies of a number of problems in transportation, communications, and other areas related to the traffic of goods, the transmission of information, etc. Many problems concerning flows are problems in linear programming and can be solved by the general methods of this theory. However, the majority of problems concerning flows admit an efficient solution by methods of graph theory.
 
A function which assigns certain numbers to the arcs of a given [[Network graph|network graph]] (directed graph). Each number is interpreted as the intensity of the flow along the given arc. Flows in a network form a convenient model in the studies of a number of problems in transportation, communications, and other areas related to the traffic of goods, the transmission of information, etc. Many problems concerning flows are problems in linear programming and can be solved by the general methods of this theory. However, the majority of problems concerning flows admit an efficient solution by methods of graph theory.
  
To each arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406601.png" /> of a network <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406602.png" /> let a non-negative real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406603.png" /> be assigned — the transmission capacity of the arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406604.png" />. The flow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406605.png" /> is said to be a stationary flow of value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406606.png" /> from a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406607.png" /> to a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406608.png" /> satisfying the restrictions on transmission capacities of the arcs if
+
To each arc $  ( x , y ) $
 +
of a network $  N $
 +
let a non-negative real number $  c ( x , y ) $
 +
be assigned — the transmission capacity of the arc $  ( x , y ) $.  
 +
The flow f ( x , y ) $
 +
is said to be a stationary flow of value $  v $
 +
from a vertex $  r $
 +
to a vertex $  s $
 +
satisfying the restrictions on transmission capacities of the arcs if
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f0406609.png" /></td> </tr></table>
+
$$
 +
f  ^ {-} ( r) - f  ^ {+} ( r)  = v ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066010.png" /></td> </tr></table>
+
$$
 +
f  ^ {-} ( x) - f  ^ {+} ( x)  = 0 \  \textrm{ for }  x \neq r , s ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066011.png" /></td> </tr></table>
+
$$
 +
f  ^ {-} ( s) - f  ^ {+} ( s)  = - v ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066012.png" /></td> </tr></table>
+
$$
 +
0 \leq  f ( x , y )  \leq  c ( x , y ) \  \textrm{ for  any  arc  }  ( x , y ) .
 +
$$
  
Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066013.png" /> is the flow leaving the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066015.png" /> is the flow entering the vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066016.png" />. In the problem of maximum flow (or max-flow problem) between two vertices, one has to construct a stationary flow from a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066017.png" /> to a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066018.png" /> of maximum possible value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066019.png" />. There are efficient algorithms to solve this problem. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066020.png" /> be a subset of vertices of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066021.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066023.png" />. Then the set of arcs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066024.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066026.png" /> is called a cut. The transmission capacity of a cut is the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066027.png" />. The following theorem on maximum flow and minimum cut (or max-flow-min-cut theorem) holds: The maximum value of a flow is equal to the minimum transmission capacity of the cuts. In applications one often uses the integrality theorem: If the transmission capacity of each arc is an integer, then there exists an integral maximum (stationary) flow.
+
Here $  f  ^ {-} ( x) = \sum _ {y} f ( x , y ) $
 +
is the flow leaving the vertex $  x $
 +
and  $  f ^ {+} ( x) = \sum _ {y} f ( y , x ) $
 +
is the flow entering the vertex $  x $.  
 +
In the problem of maximum flow (or max-flow problem) between two vertices, one has to construct a stationary flow from a vertex $  r $
 +
to a vertex $  s $
 +
of maximum possible value $  v $.  
 +
There are efficient algorithms to solve this problem. Let $  X $
 +
be a subset of vertices of $  N $
 +
such that $  r \in X $,  
 +
$  s \notin X $.  
 +
Then the set of arcs $  ( x , y ) $
 +
such that $  x \in X $,  
 +
$  y \notin X $
 +
is called a cut. The transmission capacity of a cut is the value $  \sum _ {x \in X , y \notin X }  c ( x , y ) $.  
 +
The following theorem on maximum flow and minimum cut (or max-flow-min-cut theorem) holds: The maximum value of a flow is equal to the minimum transmission capacity of the cuts. In applications one often uses the integrality theorem: If the transmission capacity of each arc is an integer, then there exists an integral maximum (stationary) flow.
  
 
A number of problems can be reduced to the problem of maximum flow between two vertices: the problem of maximum flow in a network with several sources and sinks; the problem of maximum flow in a network with non-negative lower and upper bounds on the flow along an arc; the problem of maximum flow in undirected and mixed networks; the problem of maximum flow in a network with given transmission capacities of arcs and vertices; etc.
 
A number of problems can be reduced to the problem of maximum flow between two vertices: the problem of maximum flow in a network with several sources and sinks; the problem of maximum flow in a network with non-negative lower and upper bounds on the flow along an arc; the problem of maximum flow in undirected and mixed networks; the problem of maximum flow in a network with given transmission capacities of arcs and vertices; etc.
  
The max-flow-min-cut theorem has revealed the common basis of a number of results obtained before in graph theory and combinatorial analysis. It turned out that the following theorems can be obtained as corollaries of this theorem: the maximum matching theorem for a bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]), the theorem on distinct representatives, theorems on the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066029.png" />-connectivity of graphs (see [[Graph, connectivity of a|Graph, connectivity of a]]), the theorem on the covering of a partially ordered set by a minimum number of chains, etc. Reduction of different problems to the problem of maximum flow is an important method in graph theory and combinatorial analysis.
+
The max-flow-min-cut theorem has revealed the common basis of a number of results obtained before in graph theory and combinatorial analysis. It turned out that the following theorems can be obtained as corollaries of this theorem: the maximum matching theorem for a bipartite graph (cf. [[Graph, bipartite|Graph, bipartite]]), the theorem on distinct representatives, theorems on the $  k $-
 +
connectivity of graphs (see [[Graph, connectivity of a|Graph, connectivity of a]]), the theorem on the covering of a partially ordered set by a minimum number of chains, etc. Reduction of different problems to the problem of maximum flow is an important method in graph theory and combinatorial analysis.
  
In a number of problems on flows in a network a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066030.png" /> corresponds to each arc <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066031.png" /> — the cost of transportation of a unit of goods along <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066032.png" /> — and one has to find a flow which, subject to certain constraints, minimizes the total cost of the flow. The problem of a flow of minimum cost (or min-cost-flow problem) consists in finding a stationary flow from a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066033.png" /> to a vertex <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066034.png" /> subject to constraints on the transmission capacities of the arcs and such that its absolute value is equal to a given number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066035.png" /> and its cost is minimal.
+
In a number of problems on flows in a network a number $  a ( x , y ) $
 +
corresponds to each arc $  ( x, y) $—  
 +
the cost of transportation of a unit of goods along $  ( x , y ) $—  
 +
and one has to find a flow which, subject to certain constraints, minimizes the total cost of the flow. The problem of a flow of minimum cost (or min-cost-flow problem) consists in finding a stationary flow from a vertex $  r $
 +
to a vertex $  s $
 +
subject to constraints on the transmission capacities of the arcs and such that its absolute value is equal to a given number $  v $
 +
and its cost is minimal.
  
In transportation problems the network is a bipartite graph. Vertices of one part <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066036.png" /> are interpreted as departure points for some goods, and the vertices of the other part <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066037.png" /> as destination points. Each departure point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066038.png" /> has a certain supply <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066039.png" /> and each destination point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066040.png" /> has a certain demand <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066041.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066042.png" />, the cost of transportation per unit of goods from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066043.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/f/f040/f040660/f04066044.png" />, be given. The problem consists in finding a flow of minimum cost subject to the demands at all destination points.
+
In transportation problems the network is a bipartite graph. Vertices of one part $  S _ {1} \dots S _ {m} $
 +
are interpreted as departure points for some goods, and the vertices of the other part $  T _ {1} \dots T _ {n} $
 +
as destination points. Each departure point $  S _ {i} $
 +
has a certain supply $  b _ {i} $
 +
and each destination point $  T _ {j} $
 +
has a certain demand $  c _ {j} $.  
 +
Let $  a _ {ij} $,  
 +
the cost of transportation per unit of goods from $  S _ {i} $
 +
to $  T _ {j} $,  
 +
be given. The problem consists in finding a flow of minimum cost subject to the demands at all destination points.
  
 
One can also consider multi-product flows and flows changing in time.
 
One can also consider multi-product flows and flows changing in time.
Line 25: Line 84:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.R. Ford,  D.R. Fulkerson,  "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.R. Ford,  D.R. Fulkerson,  "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
Line 33: Line 90:
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.A. Bondy,  U.S.R. Murthy,  "Graph theory with applications" , Macmillan  (1976)  pp. Chapt. 11</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T.C. Hu,  "Integer programming and network flows" , Addison-Wesley  (1969)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.K. Smith,  "Network optimization practice: a computational guide" , Chichester  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.L. Lawler,  "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.E. Tarjan,  "Data structures and network algorithms" , SIAM  (1983)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Tardos,  "A strongly polynomial minimum cost circulation algorithm"  ''Combinatorica'' , '''5'''  (1985)  pp. 247–255</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.V. Goldberg,  R.E. Tarjan,  "Finding minimum-cost circulations by successive approximation"  ''Math. of Operations Research''  (To appear)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Minieka,  "Optimization algorithms for networks and graphs" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J. Kennington,  R. Helgason,  "Algorithms for network programming" , Wiley  (1980)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.A. Bondy,  U.S.R. Murthy,  "Graph theory with applications" , Macmillan  (1976)  pp. Chapt. 11</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T.C. Hu,  "Integer programming and network flows" , Addison-Wesley  (1969)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.K. Smith,  "Network optimization practice: a computational guide" , Chichester  (1982)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.L. Lawler,  "Combinatorial optimization: networks and matroids" , Holt, Rinehart &amp; Winston  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.E. Tarjan,  "Data structures and network algorithms" , SIAM  (1983)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  E. Tardos,  "A strongly polynomial minimum cost circulation algorithm"  ''Combinatorica'' , '''5'''  (1985)  pp. 247–255</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.V. Goldberg,  R.E. Tarjan,  "Finding minimum-cost circulations by successive approximation"  ''Math. of Operations Research''  (To appear)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  E. Minieka,  "Optimization algorithms for networks and graphs" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J. Kennington,  R. Helgason,  "Algorithms for network programming" , Wiley  (1980)</TD></TR></table>
 +
 +
[[Category:Graph theory]]

Latest revision as of 20:15, 15 March 2023


A function which assigns certain numbers to the arcs of a given network graph (directed graph). Each number is interpreted as the intensity of the flow along the given arc. Flows in a network form a convenient model in the studies of a number of problems in transportation, communications, and other areas related to the traffic of goods, the transmission of information, etc. Many problems concerning flows are problems in linear programming and can be solved by the general methods of this theory. However, the majority of problems concerning flows admit an efficient solution by methods of graph theory.

To each arc $ ( x , y ) $ of a network $ N $ let a non-negative real number $ c ( x , y ) $ be assigned — the transmission capacity of the arc $ ( x , y ) $. The flow $ f ( x , y ) $ is said to be a stationary flow of value $ v $ from a vertex $ r $ to a vertex $ s $ satisfying the restrictions on transmission capacities of the arcs if

$$ f ^ {-} ( r) - f ^ {+} ( r) = v , $$

$$ f ^ {-} ( x) - f ^ {+} ( x) = 0 \ \textrm{ for } x \neq r , s , $$

$$ f ^ {-} ( s) - f ^ {+} ( s) = - v , $$

$$ 0 \leq f ( x , y ) \leq c ( x , y ) \ \textrm{ for any arc } ( x , y ) . $$

Here $ f ^ {-} ( x) = \sum _ {y} f ( x , y ) $ is the flow leaving the vertex $ x $ and $ f ^ {+} ( x) = \sum _ {y} f ( y , x ) $ is the flow entering the vertex $ x $. In the problem of maximum flow (or max-flow problem) between two vertices, one has to construct a stationary flow from a vertex $ r $ to a vertex $ s $ of maximum possible value $ v $. There are efficient algorithms to solve this problem. Let $ X $ be a subset of vertices of $ N $ such that $ r \in X $, $ s \notin X $. Then the set of arcs $ ( x , y ) $ such that $ x \in X $, $ y \notin X $ is called a cut. The transmission capacity of a cut is the value $ \sum _ {x \in X , y \notin X } c ( x , y ) $. The following theorem on maximum flow and minimum cut (or max-flow-min-cut theorem) holds: The maximum value of a flow is equal to the minimum transmission capacity of the cuts. In applications one often uses the integrality theorem: If the transmission capacity of each arc is an integer, then there exists an integral maximum (stationary) flow.

A number of problems can be reduced to the problem of maximum flow between two vertices: the problem of maximum flow in a network with several sources and sinks; the problem of maximum flow in a network with non-negative lower and upper bounds on the flow along an arc; the problem of maximum flow in undirected and mixed networks; the problem of maximum flow in a network with given transmission capacities of arcs and vertices; etc.

The max-flow-min-cut theorem has revealed the common basis of a number of results obtained before in graph theory and combinatorial analysis. It turned out that the following theorems can be obtained as corollaries of this theorem: the maximum matching theorem for a bipartite graph (cf. Graph, bipartite), the theorem on distinct representatives, theorems on the $ k $- connectivity of graphs (see Graph, connectivity of a), the theorem on the covering of a partially ordered set by a minimum number of chains, etc. Reduction of different problems to the problem of maximum flow is an important method in graph theory and combinatorial analysis.

In a number of problems on flows in a network a number $ a ( x , y ) $ corresponds to each arc $ ( x, y) $— the cost of transportation of a unit of goods along $ ( x , y ) $— and one has to find a flow which, subject to certain constraints, minimizes the total cost of the flow. The problem of a flow of minimum cost (or min-cost-flow problem) consists in finding a stationary flow from a vertex $ r $ to a vertex $ s $ subject to constraints on the transmission capacities of the arcs and such that its absolute value is equal to a given number $ v $ and its cost is minimal.

In transportation problems the network is a bipartite graph. Vertices of one part $ S _ {1} \dots S _ {m} $ are interpreted as departure points for some goods, and the vertices of the other part $ T _ {1} \dots T _ {n} $ as destination points. Each departure point $ S _ {i} $ has a certain supply $ b _ {i} $ and each destination point $ T _ {j} $ has a certain demand $ c _ {j} $. Let $ a _ {ij} $, the cost of transportation per unit of goods from $ S _ {i} $ to $ T _ {j} $, be given. The problem consists in finding a flow of minimum cost subject to the demands at all destination points.

One can also consider multi-product flows and flows changing in time.

References

[1] L.R. Ford, D.R. Fulkerson, "Flows in networks" , Princeton Univ. Press (1962)

Comments

The max-flow-min-cut theorem is due to L.R. Ford and D.R. Fulkerson.

References

[a1] J.A. Bondy, U.S.R. Murthy, "Graph theory with applications" , Macmillan (1976) pp. Chapt. 11
[a2] T.C. Hu, "Integer programming and network flows" , Addison-Wesley (1969)
[a3] D.K. Smith, "Network optimization practice: a computational guide" , Chichester (1982)
[a4] E.L. Lawler, "Combinatorial optimization: networks and matroids" , Holt, Rinehart & Winston (1976)
[a5] R.E. Tarjan, "Data structures and network algorithms" , SIAM (1983)
[a6] E. Tardos, "A strongly polynomial minimum cost circulation algorithm" Combinatorica , 5 (1985) pp. 247–255
[a7] A.V. Goldberg, R.E. Tarjan, "Finding minimum-cost circulations by successive approximation" Math. of Operations Research (To appear)
[a8] E. Minieka, "Optimization algorithms for networks and graphs" , M. Dekker (1978)
[a9] J. Kennington, R. Helgason, "Algorithms for network programming" , Wiley (1980)
How to Cite This Entry:
Flow in a network. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Flow_in_a_network&oldid=18358
This article was adapted from an original article by V.B. Alekseev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article