BLOG

Suppose there is a network of railroads and our aim is to schedule trains from a fixed origin station to the destination one. Of course, there are some cases that there are some intermediate stations between the origin and the destination station depended on the railroad network (the connection between stations). To avoid collisions, between any two stations, trains can be traversed in only one direction and we assume that this direction can carry a limited number of trains at once time. Apart from the origin and destination, the number of trains entering must be equal to the number of trains leaving in each intermediate. Our interest is to maximize the number of trains that can all together leave the origin and reach the destination. Furthermore, one might want to know more about the minimum removal of combination of tracks would prevent any trains moving from the original station to the destination and those combinations of tracks served the smallest sum of trains.
In the study of network (traffic) flow, we can represent the railroad by a directed graph where the nodes represents the stations, the edges represents the tracks connecting stations and the source and sink denotes respectively the origin and the destination. The maximum number of trains travelling in one track between any two stations is the capacity of the corresponding edge and obviously, must be non-negative. The conservation laws says that number of trains that flows into each intermediate stations equals the amount flowing out of this vertex excluding the source and sink. The objective problem is to find the maximum number of trains that can travel from the origin station to the destination station, which called by the maximum flow problem. Moreover, the problem determining the combination of edges removed having minimum capacity sum would prevent any movement from the source to the sink is called by the minimum cut problem.
Interestingly, L. R. Ford, Jr. and D. R. Fulkerson have proved that the maximum flow problem is equivalent to the problem of finding the minimum cut. In more details, the maximum flow will be equal to the minimum cut and the result is the Max-Flow Min-Cut Theorem, whose proof can be found in the reference. $$ \max_{v: (s,v) \in E} f_{sv} = \min_{(u,v) \in E} c_{uv} d_{uv} $$ where a graph \(G = (V,E)\) with \(V, E\) respectively denotes the set of vertices and edges in the graph \(G\); \(s, t \in V\) denotes the source and the sink of the graph \(G\); \(c_{uv}\) is the capacity of edges and \(f_{uv} \leq c_{uv}\) denotes the flows of the edge \(uv \in E\); and \(d_{uv}\) taking value \(1\) if the edge \(uv\) is in the cut and \(0\) otherwise.
It can be seen that the maximum flow problem and the minimum cut problem can be formulated as two primal-dual linear programs. Moreover, the equality in the max-flow and min-cut theorem agrees with the strong duality theorem in linear programming.