Consider the max-flow problem of Fig. 3.11, where s = 1 and t = 5.
(a) Enumerate all cuts of the form [S, N -S] such that 1 ∈ S and 5 ∈ S / . Calculate the capacity of each cut.
(b) Find the maximal and minimal saturated cuts.
(c) Apply the Ford-Fulkerson method to find the maximum flow and verify the max-flow/min-cut equality
![1475_e9261e95-8241-4a44-a580-11cb9f7bd214.png](https://secure.tutorsglobe.com/CMSImages/1475_e9261e95-8241-4a44-a580-11cb9f7bd214.png)