A linear programming problem in which the objective is to maximize the overall flow from an initial source to a final sink. The network consists of nodes connected by directed arcs, each arc having a given direction and a limited capacity. A cut is a line that breaks the network into two sections, one containing the source and the other containing the sink. The value of a cut is defined as the sum of the values on the broken arcs, ignoring arcs flowing from the sink section to the source section. The maximum flow can often be easily found using the maximum flow/minimum cut theorem, which states that these two quantities are equal.
Network flow problem. This simple network illustrates the fact that the maximum flow equals the minimum cut.
