2022-188

Consider the flow network in the figure, where s and t are the source and sink, respectively, with an initial flow though paths in blue and red. Choose the alternative with the pair of augmenting paths that together push the largest amount of flow in the corresponding residual graph.

1. s-A-C-F-H-D-t and s-E-C-F-H-D-t
2. s-A-C-D-t and s-E-C-F-H-D-t
3. s-E-G-I-t and s-A-C-E-G-I-t
4. s-A-C-F-H-t and s-E-C-B-D-t
5. None of the above.

Original idea by: Lucca Bavia