\(\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.5A Concrete Example

Let's apply the Labeling Algorithm to the network flow shown in Figure 13.2. Then we start with the source: \begin{equation*} S:\quad(*,+,\infty) \end{equation*} Since the source \(S\) is the first vertex labeled, it is also the first one scanned. So we look at the neighbors of \(S\) using the pseudo-alphabetic order on the vertices. Thus, the first one to be considered is vertex \(B\) and since the edge \((S,B)\) is not full, we label \(B\) as \begin{equation*} B:\quad(S,+,8). \end{equation*} We then consider vertex \(E\) and label it as \begin{equation*} E:\quad(S,+,28). \end{equation*} Next is vertex \(F\), which is labeled as \begin{equation*} F:\quad(S,+,15). \end{equation*} At this point, the scan from \(S\) is complete.

The first vertex after \(S\) to be labeled was \(B\), so we now scan from \(B\). The (unlabeled) neighbors of \(B\) to be considered, in order, are \(A\), \(C\), and \(D\). This results in the following labels: \begin{align*} A\amp:\quad(B,+,8)\\ C\amp:\quad(B,+,8)\\ D\amp:\quad(B,-,6) \end{align*} The next vertex to be scanned is \(E\), but \(E\) has no unlabeled neighbors, so we then move on to \(F\), which again has no unlabeled neighbors. Finally, we scan from \(A\), and using the pseudo-alphabetic order, we first consider the sink \(T\) (which in this case is the only remaining unlabeled vertex). This results in the following label for \(T\). \begin{equation*} T:\quad(A,+,8) \end{equation*} Now that the sink is labeled, we know there is an augmenting path. We discover this path by backtracking. The sink \(T\) got its label from \(A\), \(A\) got its label from \(B\), and \(B\) got its label from \(S\). Therefore, the augmenting path is \(P=(S,B,A,T)\) with \(\delta=8\). All edges on this path are forward. The flow is then updated by increasing the flow on the edges of \(P\) by \(8\). This results in the flow shown in Figure 13.12. The value of this flow is \(38\).

<<SVG image is unavailable, or your browser cannot render it>>

Figure13.12An Updated Network Flow

Here is the sequence (reading down the columns) of labels that will be found when the labeling algorithm is applied to this updated flow. (Note that in the scan from \(S\), the vertex \(B\) will not be labeled, since now the edge \((S,B)\) is full.) \begin{align*} S:\amp\quad(*,+,\infty)\amp D:\amp\quad(E,+,12)\\ E:\amp\quad(S,+,28)\amp A:\amp\quad(F,+,12)\\ F:\amp\quad(S,+,15)\amp C:\amp\quad(B,+,10)\\ B:\amp\quad(E,+,19)\amp T:\amp\quad(A,+,12) \end{align*} This labeling results in the augmenting path \(P=(S,F,A,T)\) with \(\delta=12\).

After this update, the value of the flow has been increased and is now \(50=38+12\). We start the labeling process over again and repeat until we reach a stage where some vertices (including the source) are labeled and some vertices (including the sink) are unlabeled.

Subsection13.5.1How the Labeling Algorithm Halts

Consider the network flow in Figure 13.13.

<<SVG image is unavailable, or your browser cannot render it>>

Figure13.13Another Network Flow

The value of the current flow is \(172\). Applying the labeling algorithm using the pseudo-alphabetic order results in the following labels (reading down the columns): \begin{align*} S:\amp\quad(*,+,\infty)\amp E:\amp\quad(I,-,3)\\ C:\amp\quad(S,+,8)\amp G:\amp\quad(E,-,3)\\ F:\amp\quad(S,+,23)\amp L:\amp\quad(E,+,3)\\ H:\amp\quad(C,+,7)\amp B:\amp\quad(G,+,3)\\ I:\amp\quad(H,+,7)\amp T:\amp\quad(L,+,3) \end{align*} These labels result in the augmenting path \(P=(S,C,H,I,E,L,T)\) with \(\delta =3\). After updating the flow and increasing its value to \(175\), the labeling algorithm halts with the following labels: \begin{align*} S:\amp\quad(*,+,\infty)\amp H:\amp\quad(C,+,4)\\ C:\amp\quad(S,+,5)\amp I:\amp\quad(H,+,4)\\ F:\amp\quad(S,+,23) \end{align*} Now we observe that the labeled and unlabeled vertices are \(L=\{S,C,F,H,I\}\) and \(U=\{T,A,B,D,E,G,J,K\}\). Furthermore, the capacity of the cut \(V=L\cup U\) is \begin{equation*} 41+8+23+8+13+29+28+25 = 175. \end{equation*} This shows that we have found a cut whose capacity is exactly equal to the value of the current flow. In turn, this shows that the flow is optimal.