Applied Combinatorics

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