Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

network flow
graph

What is the max-flow, min-cut theorem?

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.

Overview

The network discussed here is a directed graph G = (V, E) of vertices connected by edges with weights. Data flows from a sourceall edges are outgoing node (In-degree 0) to a sink all edges are incomingnode (Out-degree 0). Each weight denotes the capacity 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.

Flow

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.

Cut

An s-t cut is partitioning the graph into two disjoint subsetsintersection is null or no common element, with the source in one part and sink in another. A cut will only be valid if it completely separates the source from the sink such as there is no path connecting the two. Alternatively, a cut is a set of edges whose removal divides the network into two halves X and Y, where s ∈ X and t ∈ Y. Moreover, a cut has a capacity that is equal to the sum of the capacities of the edges in the cut.

Goal

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

Example

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

1 of 9

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

Application

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

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.

Keep Exploring