Flows and cuts

In this chapter, we focus on the following two problems:

• Finding a maximum flow: What is the maximum amount of flow we can send from a node to another node?
• Finding a minimum cut: What is a minimum-weight set of edges that separates two nodes of the graph?

The input for both these problems is a directed, weighted graph that contains two special nodes: the source is a node with no incoming edges, and the sink is a node with no outgoing edges.

As an example, we will use the following graph where node 1 is the source and node 6 is the sink:

Maximum Flow

In the maximum flow problem, our task is to send as much flow as possible from the source to the sink. The weight of each edge is a capacity that restricts the flow that can go through the edge. In each intermediate node, the incoming and outgoing flow has to be equal.

For example, the maximum size of a flow in the example graph is 7. The following picture shows how we can route the flow:

The notation $v/k$ means that a flow of $v$ units is routed through an edge whose capacity is $k$ units. The size of the flow is $7$, because the source sends $3+4$ units of flow and the sink receives $5+2$ units of flow. It is easy see that this flow is maximum, because the total capacity of the edges leading to the sink is $7$.

Minimum Cut

In the minimum cut problem, our task is to remove a set of edges from the graph such that there will be no path from the source to the sink after the removal and the total weight of the removed edges is minimum.

The minimum size of a cut in the example graph is 7. It suffices to remove the edges $2 \rightarrow 3$ and $4 \rightarrow 5$:

After removing the edges, there will be no path from the source to the sink. The size of the cut is $7$, because the weights of the removed edges are $6$ and $1$. The cut is minimum, because there is no valid way to remove edges from the graph such that their total weight would be less than $7$.

It is not a coincidence that the maximum size of a flow and the minimum size of a cut are the same in the above example. It turns out that a maximum flow and a minimum cut are always equally large, so the concepts are two sides of the same coin.

Next we will discuss the Ford–Fulkerson algorithm that can be used to find the maximum flow and minimum cut of a graph. The algorithm also helps us to understand why they are equally large.