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. 1  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

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

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{.}$