2022-190

Consider the flow network below with source 1 and sink 10, where the capacities are shown besides each link.

Select the correct alternative containing the maximum flow through this network and possible flow values from node 1 to nodes 2, 4, and 3, respectively, in a max flow solution.

1. The maximum flow of the network is 19 and the flow values from node 1 are 8, 5, and 9.
2. The maximum flow of the network is 18 and the flow values from node 1 are 7, 5, and 6.
3. The maximum flow of the network is 20 and the flow values from node 1 are 7, 5, and 8.
4. The maximum flow of the network is 19 and the flow values from node 1 are 7, 5, and 7.
5. None of the above.

Original idea by: Rubens de Castro Pereira