Answer:
Check the explanation
Step-by-step explanation:
1) Algorithm for finding the new optimal flux: 1. Let E' be the edges eh E for which f(e)>O, and let G = (V,E). Find in Gi a path Pi from s to u and a path , from v to t.
2) [Special case: If , and
have some edge e in common, then Piu[(u,v)}uPx has a directed cycle containing (u,v). In this instance, the flow along this cycle can be reduced by a single unit without any need to change the size of the overall flow. Return the resulting flow.]
3) Reduce flow by one unit along
4) Run Ford-Fulkerson with this sterling flow.
Justification and running time: Say the original flow has see F. Lees ignore the special case (4 After step (3) Of the elgorithuk we have a legal flaw that satisfies the new capacity constraint and has see F-1. Step (4). FOrd-Fueerson, then gives us the optimal flow under the new cePacie co mint. However. we know this flow is at most F, end thus Ford-Fulkerson runs for just one iteration. Since each of the steps is linear, the total running time is linear, that is, O(lVl + lEl).