Max-Flow Min-Cut Theorem
The Max-Flow Min-Cut Theorem is a fundamental principle in network flow theory. It states that in a flow network, the maximum amount of flow that can be sent from a source node to a sink node is equal to the capacity of the smallest cut that separates these two nodes. A cut is a partition of the network's nodes into two disjoint sets, where one set contains the source and the other contains the sink.
This theorem is crucial in various applications, including telecommunications, transportation, and logistics. It helps in optimizing resource allocation and understanding the limits of network capacities. The theorem was first proven by L. R. Ford Jr. and D. R. Fulkerson in the 1950s, establishing a strong connection between flow and cut in networks.