SKEDSOFT

Problem . Find a maximum flow in the directed network shown in Fig. (4.74) and prove that it is a maximum.

Solution. We start by sending a flow of 2 units through the path sadt, a flow of 3 units through sbet, and a flow of 3 units through scft, obtaining the flow shown on the left in Fig. (4.75). Continue by sending flows of 2 units through sbdt and 2 units through sbft, obtaining the flow shown on the right in Fig. (4.75)

At this point, there are no further flow-augmenting chains from s to t involving only forward arcs. However, we can use the backward arc da to obtain a flow-augmenting chain scbdaet. Since the slack of this chain is 2, we add a flow of 2 to sc, cb, bd, ae, and et, and subtract 2 from ad.
The result is shown in Fig. (4.76).

A search for further flow-augmenting chains takes us from s to c or b and on to d, where we are stuck.
This tells us that the current flow (of value 14) is maximum.
It also presents us with a cut verifying maximality, namely, S = {s, b, c, d} (those vertices reachable from s by flow-augmenting chains) and T = {a, e, f, t} (the complement of s). The capacity of this cut is
C_sa C_be C_bf C_cf C_dt = 2 3 2 3 4 = 14.
Since this is the same as the value of the flow, we have verified that our flow is maximum.