## 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:

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

We then consider vertex $E$ and label it as

Next is vertex $F\text{,}$ which is labeled as

At this point, the scan from $S$ is complete.

The first vertex after $S$ to be labeled was $B\text{,}$ so we now scan from $B\text{.}$ The (unlabeled) neighbors of $B$ to be considered, in order, are $A\text{,}$ $C\text{,}$ and $D\text{.}$ This results in the following labels:

The next vertex to be scanned is $E\text{,}$ but $E$ has no unlabeled neighbors, so we then move on to $F\text{,}$ which again has no unlabeled neighbors. Finally, we scan from $A\text{,}$ 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\text{.}$

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\text{,}$ $A$ got its label from $B\text{,}$ and $B$ got its label from $S\text{.}$ Therefore, the augmenting path is $P=(S,B,A,T)$ with $\delta=8\text{.}$ All edges on this path are forward. The flow is then updated by increasing the flow on the edges of $P$ by $8\text{.}$ This results in the flow shown in Figure 13.12. The value of this flow is $38\text{.}$

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\text{,}$ the vertex $B$ will not be labeled, since now the edge $(S,B)$ is full.)

This labeling results in the augmenting path $P=(S,F,A,T)$ with $\delta=12\text{.}$

After this update, the value of the flow has been increased and is now $50=38+12\text{.}$ 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.

The value of the current flow is $172\text{.}$ Applying the labeling algorithm using the pseudo-alphabetic order results in the following labels (reading down the columns):

These labels result in the augmenting path $P=(S,C,H,I,E,L,T)$ with $\delta =3\text{.}$ After updating the flow and increasing its value to $175\text{,}$ the labeling algorithm halts with the following labels:
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\}\text{.}$ Furthermore, the capacity of the cut $V=L\cup U$ is