Flow
A flow network: a directed graph where each edge has a capacity (the maximum flow that it can carry).
Maximum flow: max amount of flow that can be sent from the source to the sink without violating any capacity constraints on the edges.
Cut
A cut in a flow network is a way of “cutting” the graph into two disjoint subsets: one containing the source and the other containing the sink.
Capacity of the cut: sum of the capacities of the edges that cross the cut from the source side to the sink side.
Minimum cut: the cut with the smallest possible capacity that, if you remove the edges in this cut, would completely block any flow from reaching the sink.
Max-Flow Min-Cut Theorem
max flow = min cut
E.g. imagine a network of water pipes:
• Nodes represent junctions. • Edges represent pipes with a maximum capacity of water they can carry. • The source is where water enters the network, and the sink is where water exits.
We want to find the maximum amount of water (max flow) we can send from the source to the sink without exceeding the capacity of any pipe.
A cut represents a potential “blockade” that, if completely shut, would stop the flow from reaching the sink. The capacity of a cut is the total capacity of all the pipes in the cut.
The maximum water flow possible in the network is exactly equal to the smallest “blockade” that, if shut, would stop any water from reaching the sink.
Applications:
• Network Routing: Ensuring efficient data transfer in computer networks. • Bipartite Matching: Solving matching problems where nodes represent entities and edges represent possible matches. • Supply Chain Optimization: Managing the flow of goods to optimize production and distribution.