Example 13.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{.}\)