Skip to main content



The Origin of the Study of Network Flow

Suppose you have a network of railroads and you want to transport trains from an origin station to a different station that we’ll call the destination station.  There are some intermediate stations in between connected via a railroad track.  To avoid collisions, trains can only travel in one direction between any two stations.  Since trains can only start at the origin and end at the destination, for each intermediate station the number of trains entering must be equal to the number of trains leaving. Each path connecting two stations can carry a certain number of trains at time. You are interested in knowing what is the maximum number of trains that can leave the origin at the same time (not staggered) and eventually reach the destination. You might also want to know which combinations of tracks, if removed, would prevent any movement from the origin to the destination, and of those combinations which had the smallest sum of trains they could support.

In the study of flow network, the railroad system would be represented by a directed graph where the stations correspond to vertices and the tracks connecting them correspond to edges.  The origin station is called the source and destination station is called the sink.  The number of trains a track can hold is the capacity of that edge and must be non-negative.  The problem of finding the maximum number of trains that can travel from the origin to the destination is the maximum flow problem.  The minimum cut problem is to determine the minimum capacity (sum of the capacity of the edges) that can be removed that prevent movement from the source to the sink.

Interestingly enough, the problem of finding the maximum flow is the same problem as that of finding the minimum cut.  L. R. Ford, Jr. and D. R. Fulkerson proved that these are equivalent problems and that the maximum flow will also be equal to the minimum cut.  This result is called the Max-Flow Min-Cut Theorem. [3]

The original inspiration for studying these questions comes from the Cold War. During the Cold War, the US military was interested in the Soviet Union Railway System that connected the Western Soviet Union to Eastern Europe, in particular East Germany.  They were interested in knowing what was the minimum number of places on the railroad system they could bomb that would completely and accurately prevent movement between the Soviet Union and Eastern Europe. [1]

To accomplish this goal, the US Air Force requested a secret report which was written in 1955 by T.E. Harris and F.S. Ross entitled Fundamentals of a Method for Evaluating Rail Net Capacities. In this report, Harris and Ross formally defined the max flow problem, in the context of the Soviet Railway. [1]

Harris and Ross did not find a method that was guaranteed to find an optimal solution.  The technique they described is to use a greedy algorithm of pushing as much flow as possible through the network until there is a bottleneck.  A bottleneck is a vertex that has more flowing coming in to it than is able to leave.  The excess flow at the bottleneck is returned to the origin and attempted to be pushed through again.  One of the benefits of their solution was described Boldyreff in 1955 as ‘The mechanics of the solutions is formulated as a simple game which can be taught to a ten-year-old boy in a few minutes. ’ [1]

While the technique described by Harris and Ross did not guarantee an optimal solution, their paper inspired Ford and Fulkerson to work on the problem.  Ford and Fulkerson developed the Ford-Fulkerson algorithm for finding the maximum flow which relies on finding augmenting paths in the network. The Ford-Fulkerson algorithm does guarantee an optimal solution. [4]

Network flow relates to what we are learning in Networks in several ways.  For instance, the maximum flow and minimum cut are properties of a network and help us understand characteristics of the network. An example of a usage that relates to this is that finding an optimal bipartite matching (for some definition of optimal) can be formulated as a maximum flow problem. Ford-Fulkerson algorithm relies heavily on use of augmenting paths, the same sort of augmenting paths we have been learning about and using in class.

Over the last 60 years the study of flow graphs have continued and have led to many significant results and applications.  As mentioned above, bipartite matching problems can be solved using a network flow graph.  Airline scheduling, image segmentation, and sports team elimination can all be formulated as max flow problems. [2]

 

[1] Schrijver, Alexander. “On the history of the transportation and maximum flow problems.” Mathematical Programming 91.3 (2002): 437-445.

[2] http://en.wikipedia.org/wiki/Maximum_flow_problem

[3] http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

[4] http://en.wikipedia.org/wiki/Ford–Fulkerson_algorithm

 

Comments

Leave a Reply

You must be logged in to post a comment.