2022-191

Which edge, when removed, results in the lowest maximum flow from s to t?

1. Edge with cost 1
2. Edge with cost 2
3. Edge with cost 3
4. Edge with cost 4
5. None of the above

Original idea by: Matheus Fernandes Sarmento

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

2022-189

Goods are transported by trucks from two orchards to three retailers. Some of the orchards cannot ship directly to some of the retailers. The capacities of the routes are limited by the number of trucks available and the number of trips made daily.  The following table shows in the margins the daily amounts of supply at the orchards and demand at the farms. The cell entries of the table specify the daily capacities of the associated routes.  All figures are in number of container boxes.

Determine the maximum amount of container boxes that can be shipped daily from orchards to retailers.

A. 24

B. 10

C. 54

D. 17

E. None of the above.

Original idea by: Muhammad Idrees

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

2022-187

What is the maximum flow from S to T in the network from Figure 1?

Fig. 1: A flow network.

1. 19.
2. 20.
3. 21.
4. 22.
5. None of the above.

Original idea by: Gabriel Oliveira