Trusted answers to developer questions

Muhammad Sulaiman Javed

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

The **max-flow, min-cut theorem** states that the maximum flow from a given source to a given sink in a network is equal to the minimum sum of a cut that separates the source from the sink.

The network discussed here is a directed graph G = (V, E) of vertices connected by edges with weights. Data flows from a ** **node (In-degree 0) to a ** **of the edge that represents the maximum flow through that edge. The theorem connects two quantities, maximum flow and minimum capacity cut. To further elaborate, we need to define the concept of flow and a cut.

For simplicity, **flow** can be imagined as a physical flow of a fluid through the network that moves from source to sink through the directed edges. Each edge will have a flow that cannot be greater than the edgeâ€™s capacity. Think of it as water flowing through a pipe, where the flow cannot be greater than the pipeâ€™s capacity.

An **s-t cut **is partitioning the graph into two **capacity **that is equal to the sum of the capacities of the edges in the cut.

The goal is to find the minimum capacity cut that will dictate the maximum flow achievable in a flow network.

Let's look at an example of how to find a minimum cut in a network graph.

Note:We can also verify this theorem using the Ford-Fulkerson algorithm that finds the maximum flow in a network.

It is widely used in computer networks to maintain reliability and connectivity and used in Bipartite matching to match graphs. Â

RELATED TAGS

network flow

graph

CONTRIBUTOR

Muhammad Sulaiman Javed

Grokking Modern System Design Interview for Engineers & Managers

Keep Exploring

Related Courses