Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section13.2Flows and Cuts

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

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

Proof
Discussion13.5

Bob's getting a bit of a sense of déjà vu after reading Theorem 13.4. He remembers from Chapter 5 that the maximum size of a clique in a graph is always at most the minimum number of colors required to properly color the graph. However, he also remembers that there are graphs without cliques of size three but with arbitrarily large chromatic number, so he's not too hopeful that this theorem is going to help out much here. Yolanda chimes in with a reminder of Chapter 6, where they learned that the maximum size of an antichain in a poset is equal to the minimum number of chains into which the ground set of the poset can be partitioned. Alice points out that Yolanda's statement is still true if the words “chain” and “antichain” are swapped. This sparks some intense debate about whether the maximum value of a flow in a network must always be equal to the minimum capacity of a cut in that network. After a while, Carlos suggests that continuing to read might be the best idea for resolving their debate.