Question

In a maximum flow network problem, what is the mathematical relationship between the max-flow value and the capacity of the minimum cut?

Accepted Answer

In a maximum flow network problem, the Max-Flow Min-Cut Theorem states that the maximum amount of flow that can pass from a source node to a sink node is exactly equal to the total capacity of the minimum cut. A flow network is a directed graph where each edge has a capacity representing the maximum amount of flow it can transmit. A source is a node where flow originates, and a sink is a node where flow terminates. A cut is a partition of the nodes into two distinct sets such that the source is in one set and the sink is in the other. The capacity of a cut is the sum of the capacities of all edges that go from the source-side set to the sink-side set. A minimum cut is the specific cut among all possible cuts that has the smallest total capacity. For example, if you have a system of pipes with various sizes and you want to send water from start to finish, the bottleneck of the entire system will always limit the maximum flow. The minimum cut represents that bottleneck, meaning you cannot send more water than the total capacity of the narrowest point, and you can always send exactly that much.

Home → All Courses → Science and Mathematics Courses → Decision Science and Optimization → Flashcard

In a maximum flow network problem, what is the mathematical relationship between the max-flow value and the capacity of the minimum cut?