Considering the applications suggested at the beginning of the chapter, it is natural to ask for the maximum value of a flow in a given network. Put another way, we want to find the largest number \(v_0\) so that there exists a flow \(\phi\) of value \(v_0\) in the network. Of course, we not only want to find the maximum value \(v_0\text{,}\) but we also want to find a flow \(\phi\) having this value. Although it may seem a bit surprising, we will develop an efficient algorithm which both finds a flow of maximum value *and* finds a certificate verifying the claim of optimality. This certificate makes use of the following important concept.

A partition \(V=L\cup U\) of the vertex set \(V\) of a network with \(S\in L\) and \(T\in U\) is called a *cut*. The *capacity* of a cut \(V=L\cup U\text{,}\) denoted \(c(L,U)\text{,}\) is defined by

\begin{equation*}
c(L,U) = \sum_{x\in L,y\in U} c(x,y).
\end{equation*}
Put another way, the capacity of the cut \(V=L\cup U\) is the total capacity of all edges *from* \(L\) *to* \(U\text{.}\) Note that in computing the capacity of the cut \(V=L\cup U\text{,}\) we only add the capacities of the edges from \(L\) to \(U\text{.}\) We do *not* include the edges from \(U\) to \(L\) in this sum.

#####
Example13.3

Let's again take a look at the network in Figure 13.2. Let's first consider the cut \(V=L_1\cup U_1\) with

\begin{equation*}
L_1 = \{S,F,B,E,D\}\qquad\text{and} \qquad U_1= \{A,C,T\}.
\end{equation*}
Here we see that the capacity of the cut is

\begin{equation*}
c(L_1,U_1) = c(F,A) + c(B,A) + c(B,C)+ c(D,C) = 24+15+20+42 =
101.
\end{equation*}
We must be a bit more careful, however, when we look at the cut \(V=L_2\cup U_2\) with

\begin{equation*}
L_2 = \{S,F,B,E\}\qquad\text{and} \qquad U_2=\{A,D,C,T\}.
\end{equation*}
Here the capacity of the cut is

\begin{equation*}
c(L_2,U_2) = c(F,A) + c(B,A) + c(B,C) + c(E,D) = 24+15+20+20=79.
\end{equation*}
Notice that we do not include \(c(D,B)\) in the calculation as the directed edge \((D,B)\) is from \(U_2\) to \(L_2\text{.}\)

The relationship between flows and cuts rests on the following fundamentally important theorem.

#####
Theorem13.4

Let \(\GVE\) be a network, let \(\phi\) be a flow in \(\bfG\text{,}\) and let \(V=L\cup U\) be a cut. The value of the flow is at most as large as the capacity of the cut.

##### Proof

In this proof (and throughout the chapter), we adopt the very reasonable convention that \(\phi(x,y)=0\) if \((x,y)\) is not a directed edge of a network \(\bfG\text{.}\)

Let \(\phi\) be a flow of value \(v_0\) and let \(V=L\cup U\) be a cut. First notice that

\begin{equation*}
v_0 = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S),
\end{equation*}
since the second summation is \(0\text{.}\) Also, by the second of our flow conservation laws, we have for any vertex other than the source and the sink,

\begin{equation*}
\sum_{y\in V}\phi(x,y) -\sum_{z\in V}\phi(z,x) = 0.
\end{equation*}
Now we have

\begin{align*}
v_0 \amp = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S)\\
\amp = \sum_{y\in V} \phi(S,y) - \sum_{z\in V}\phi(z,S) +
\sum_{\substack{x\in L\\x\neq S} }\left[\sum_{y\in V} \phi(x,y) -
\sum_{z\in V}\phi(z,x)\right]\\
\amp = \sum_{x\in L}\left[\sum_{y\in V} \phi(x,y) -
\sum_{z\in V}\phi(z,x)\right]
\end{align*}
At this point, we want to pause and look at the last line. Notice that if \((a,b)\) is a directed edge with both endpoints in \(L\text{,}\) then when the outer sum is conducted for \(x=a\text{,}\) we get an overall contribution of \(\phi(a,b)\text{.}\) On the other hand, when it is conducted for \(x=b\text{,}\) we get a contribution of \(-\phi(a,b)\text{.}\) Thus, the terms cancel out and everything simplifies to

\begin{equation*}
\sum_{\substack{x\in L\\y\in U} } \phi(x,y) - \sum_{\substack{x\in
L\\ z\in U} } \phi(z,x)\leq \sum_{\substack{x\in L\\y\in U} }
\phi(x,y)\leq \sum_{\substack{x\in L\\y\in U} } c(x,y)=c(L,U).
\end{equation*}
Thus \(v_0\leq c(L,U)\text{.}\)