Build fluency in the vocabulary of the equivalence between a network's maximum flow and its minimum disconnecting cut.
0 / 5 completed
1 / 5
A teammate explains that in a flow network, the maximum amount of flow that can be pushed from a source to a sink is always exactly equal to the minimum total capacity of edges that, if removed, would disconnect the source from the sink. What theorem is being described?
The max-flow min-cut theorem is exactly this: it proves that the maximum flow achievable from a source to a sink in a flow network always exactly equals the minimum total capacity of edges whose removal disconnects the source from the sink. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This flow-equals-cut equivalence is exactly why algorithms that compute maximum flow, such as Ford-Fulkerson, simultaneously reveal the network's minimum bottleneck cut.
2 / 5
During a design review, the team models a network's link capacities as a flow network and computes the maximum flow to identify the exact set of links that form the network's true bottleneck. Which capability does this provide?
Computing maximum flow here provides identification of the minimum-capacity cut that limits throughput, since the max-flow min-cut theorem guarantees this cut's capacity exactly equals the computed maximum flow. Simply summing every link's capacity in the network ignores the topology entirely and would not reveal which specific links form the true bottleneck. This flow-reveals-the-bottleneck-cut behavior is exactly why max-flow min-cut is used to locate capacity constraints in real networks.
3 / 5
In a code review, a dev notices a capacity-planning tool sums every link's raw capacity in the network to estimate throughput, instead of computing max-flow to find the true minimum-capacity cut that actually limits end-to-end throughput. What does this represent?
This is a missed max-flow min-cut opportunity, since computing max-flow would reveal the true bottleneck cut instead of the misleading sum of every link's raw capacity. A cache eviction policy is an unrelated concept about discarded cache entries. This sum-every-link's-capacity pattern is exactly the kind of misleading estimate a reviewer flags once the actual topological bottleneck is what matters.
4 / 5
An incident report shows a capacity-planning estimate overstated real throughput by a wide margin, because it summed every link's raw capacity instead of accounting for the topology's actual bottleneck cut. What practice would prevent this?
Computing the network's max-flow lets the max-flow min-cut theorem's equivalence reveal the true minimum-capacity cut limiting real throughput. Continuing to sum every link's raw capacity regardless of how the network's topology actually constrains real throughput is exactly what caused the overstated estimate described in this incident. This compute-max-flow approach is the standard fix once raw capacity sums are confirmed to ignore the network's actual bottleneck.
5 / 5
During a PR review, a teammate asks why the team reaches for max-flow min-cut analysis instead of just inspecting the network diagram visually to guess the bottleneck, given that visual inspection is quicker for small diagrams. What is the reasoning?
Max-flow min-cut analysis trades some computation for a mathematically guaranteed bottleneck identification, while visual inspection is quicker for small diagrams but becomes unreliable and error-prone as the network grows in size and interconnection. This is exactly why max-flow min-cut analysis is favored for large or complex networks, while eyeballing a diagram might suffice only for a tiny, simple topology.