Flow in a network

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)