2026-341

 In the study of Network Flow, the Ford-Fulkerson algorithm relies on constructing a Residual Network  from an original flow network  and a valid flow . Below is the Residual Graph () generated from an unknown flow network.

Which of the following pairs of Original Network  (left) and Flow  (right) correctly generated the Residual Graph above?

Pair I:

Pair II:

Pair III:

Pair IV:

The alternative that contains a correct statement is:

1. Only pair II is correct.
2. Only pairs I and III are correct.
3. Only pair I is correct.
4. Only pairs II and IV are correct.
5. None of the above.

Original idea by: Yuri S. Costa

2026-340

During a peak usage period following a power outage, the network of a community center began operating using packet switching, where data is divided into small packets and transmitted across the network, and bandwidth is provided on demand.

The infrastructure is composed of devices interconnected by links with limited capacities. Each link has a maximum transmission capacity in (MB/s), representing how much data can be transmitted. The main objective of the system is to maximize the total flow of data (packets) sent from S to T.

Since packets can follow different paths to reach the destination, the network can be modeled as a directed graph. To ensure the best possible performance, we aim to determine the maximum flow of packets that can be transmitted from the source to the destination.  A schematic drawing of the community center's network with capacities is given below.

Which of the following alternatives represents a maximum flow of data sent from S to T?

a)



b) 

  


c) 

d)



e) None of the above.

Original idea by: Tássia Martins

2026-339

Cynthya is a big fan of the band Suplaz, which rarely performs in Brazil. She just found out they’ll be at Rock in Rio festival and is thrilled. She is the manager of the Capanema Suplaz fan group, so she decides to organize transportation to help as many fans as possible from her city attend the concert. 

Since the trip is long, she sets up a system of shared rides and transfers: fans can travel between cities using different cars, vans, or buses, meeting at stops along the way. At each segment of the trip, there is a limit to how many people can be transported, depending on vehicle availability. Fans may switch vehicles at intermediate stops.

The figure above represents this transportation system as a directed network. Capanema is the source (S) and Rio is the sink (T). The intermediate nodes (A, B, C, and D) represent transfer points, like hotels or meeting locations. Each edge has a capacity, indicating the maximum number of people that can travel along that segment.

What is the maximum flow from Capanema to Rio, which corresponds to the maximum number of fans that can be transported?

A) 8

B) 10

C) 20

D) 12

E) None of the above

Original idea by: Melissa Araújo

2026-338

As a resistance leader, you have obtained a schematic map of the dictatorship communication cables. Because of the technology used, the signal travels one-way only, as depicted in the map. To launch your attack, you must completely cut all paths from the Capital (s) to the Military Base (t).

Each one-way cable is guarded. The cost to destroy a cable (in C4 charges and personnel) is shown in the map. You have a total budget of B = 10.

---

Problem Statement

Which of the following statements is true regarding your sabotage plan?

a) The cheapest way to disconnect the base costs 11, so your budget of B = 10 is not enough to go through with the plan.

b) You can successfully implement the plan for a cost of 9 by destroying the cables (a, t) and (b, t).

c) The most efficient plan is to hit cables (s, b) and (b, a), which only costs 10 and leaves the base isolated.

d) You would need to destroy every cable connected to the Capital, costing you exactly 18.

e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-337

On Easter Sunday, due to high demand, airlines had to limit the number of planes that could fly over certain regions. Help Zula Airlines maximize the number of planes that could travel on April 4, 2026, at 2 PM, through the areas shown in the figure below, where SP is the source node and AM is the sink node. In this network flow problem, what would be the residual network formed from the flows and capacities shown?

 

a.) 

b.) 

c.) 

d.) 

e) None of the above

Original idea by: Julia de Pietro Bigi

2026-336

A research data center needs to transfer data to a remote backup facility during a 4‑hour maintenance window. The data transfer process is modeled as a directed network, where nodes represent logical components (functional stages) of the data transfer pipeline, and edges represent logical communication channels, with limited capacity.

In this model, node \(A\) represents the point where data is generated in the primary data center. The intermediate nodes (\(B, C, D\)) represent functional stages of the transfer process, such as internal processing, aggregation, or interfaces to external networks. And node \(E\) represents the logical destination where data is finally stored at the backup site.

All edges have constant transmission capacity, except for one critical link, whose capacity varies over time due to shared usage with other services. The network links are as follows, with capacities measured in GB/hour:

\( A \rightarrow B : 8 \)

\( B \rightarrow C : 4 + \pi \sin(\pi t/4) \)

\( C \rightarrow E : 9 \)

\( A \rightarrow D : 3 \)

\( D \rightarrow E : 6 \)

where \(t\) is the time in hours since the start of the maintenance window.

Which of the following alternatives represents approximately the maximum total amount of data (in GB) that can be transferred from \(A\) to \(E\) during the maintenance window?

a) 40

b) 36

c) 28

d) 18

e) None

 

Original idea by: Ingrid Barbosa

2025-275

The following image illustrates the Push-Relabel algorithm partially executed on a flow graph, with the respective residual graph displayed on the right. The algorithm repeatedly performs relabel and push operations on a node, trying to push as much flow as possible to neighbors in alphabetical order. A FIFO queue of active nodes (the ones that have excess flow) is used to select the next node to act upon, initialized with the source only.  If a node cannot push all its excess flow, it returns to the FIFO queue.

Based on the process illustrated, mark the correct alternative of the next step in the algorithm:

a) Relabeling of 'a', setting 'h' to 8, and returning the excess flow to 'S' using Push.

b) Relabeling of 'c', setting 'h' to 2, and returning the excess flow to 'b' using Push.

c) Relabeling of 'c', setting 'h' to 8, and returning the excess flow to 'S' using Push.

d) Relabeling of 'e', setting 'h' to 1, and pushing the excess flow to 't'.

e) None of the above 

 

 Original idea by: Giorgio Rossa

2025-267

The contractors for the new Alphaville Barão Geraldo luxury allotment have hired the brilliant students of the MO412 class to design a high-capacity water distribution network. The project's goal is to pump water from the campus lake (Node Lago) through a series of seven interconnected retention dams (Nodes A through G) to the development site (Node Alpha).

The contract specifies that the network must be able to deliver a minimum of 30,000 liters of water per minute. The students have produced the following design, with pipe capacities also measured in thousands of liters per minute:

Analyze the following propositions regarding the network's performance and limitations.

1. Suppose that, due to budget cuts, the pipe from Dam E to Dam G must be downgraded to a capacity of 5,000 L/min. With this hypothetical change, the contractual minimum delivery of 30,000 liters/minute would still be met.
2. To improve performance, a proposal is made to upgrade the pipe from Dam A to Dam D to a capacity of 18,000 L/min. This upgrade alone is sufficient to increase the network's total maximum flow.
3. If a critical failure shuts down the pipe from the Lago to Dam A (capacity becomes 0 L/min), the contractual minimum of 30,000 L/min can still be satisfied by rerouting flow through Dam B.
4. In the original, unmodified network, the pipe connecting Dam D to Dam F must operate at its full capacity of 5,000 L/min in order to achieve the maximum network flow.

Based on your analysis, choose the correct option:

1. Only proposition I is correct.
2. Only proposition II is correct.
3. Only propositions I, III, and IV are correct.
4. Only propositions II and III are correct.
5. None of the above

Original idea by: Eduardo Bouhid

2025-266

In the study of network flows, the residual network plays a key role in maximum flow algorithms such as Ford-Fulkerson, Edmonds–Karp, and Dinitz. Which of the following statements best describes the residual network and its importance?

1. The residual network contains only the edges from the original graph with unchanged capacities, and it is used to verify whether the minimum cut has been reached.
2. The residual network augments the original graph by duplicating every edge, regardless of the current flow, in order to balance the inflow and outflow of intermediate nodes.
3. The residual network includes forward and backward edges that represent the remaining available capacity and the possibility of canceling part of the existing flow, enabling the search for augmenting paths.
4. The residual network is constructed only once at the beginning of the algorithm and remains fixed throughout the process, guaranteeing polynomial complexity.
5. None of the above.

Original idea by: Pedro Pereira

2025-265

The figure below shows a power transmission network. Nodes G1 and G2 are generators; C1 and C2 are consumers. The numbers on the edges are the maximum capacities (MW) of the transmission lines.    

What is the maximum total flow that can be delivered from the generators (G1, G2) to the consumers (C1, C2)?

Alternatives:

A) 25 MW

B) 30 MW

C) 35 MW

D) 40 MW

E) None of the above

Original idea by: Giancarlo Maldonado Cárdenas

2023-228

A company launched a new gadget C to be produced globally for North American and South American markets.

The company uses just-in-time as a logistic strategy with no warehouse. Still, it has a quality control standard with the assistance of laboratories in the United Kingdom, Spain, and South Africa.

The company has some contractors in the Asia-Pacific region that make two types of components, A and B, to create the C product.  In order to produce one container of product C, two containers of component A and three containers of component B are necessary.

In the graph above, we show the logistic circuit of factories, ensemble centers (located in Singapure, Dubai , and Egypt), quality control labs, and consumer centers for this operation.  The production flow of component A (blue arrows), component B (red arrows), and the distribution flow (purple arrows) is shown. The numbers near the arrows show the capacity to transport from one location to another.

Which of the statements below are compatible with a production and distribution scheme in the manufacturing supply chain that delivers the maximum quantity of gadgets while producing the minimum amount of components?

1. New York gets 20 gadgets, Japan produces 42 components B, and Australia produces 22 components A.
2. Sao Paulo gets 9 gadgets, India produces 75 components B, and Hong Kong produces 50 components A.
3. Sao Paulo gets 10 gadgets, India produces 74 components B, and Hong Kong produces 45 components A
4. New York gets 18 gadgets, Japan produces 40 components B, and Australia produces 20 components A

Chose the right answer.

1. I
2. I and II
3. II and IV
4. III and IV
5. None of the above.

Original idea by: Alexander Valle Rey

2023-227

Consider a flow network for the company "A", which needs to deliver products from the capital to 10 cities. Three of these cities are small and don't have direct delivery routes from the capital. However, each of these small cities can receive products from the other 7 cities.

Due to a special event, City "T", one of the three small cities, requires a delivery of 650 products. The flow capacities of the network are defined as follows:

• Company "A" can send a maximum of 150 products to each city that has a direct connection from the capital.
• Two of the 7 cities that can receive products directly from the capital can forward a maximum of 200 products each to City "T".
• The remaining 5 of the 7 cities can forward a maximum of 50 products each to City "T".
• The other two small cities don't require any products.

Given these conditions, how many of the 650 requested products can be delivered to City "T" for the event?

1. 500
2. 550
3. 600
4. 650
5. None of the above

Original idea by: Thaysa Bello

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

2022-126

Consider the statements below about network flows, where s is the source and t the sink:

I) The maximal flow in the following network is 10:

II) Given the following graph with flow/capacity for each link:

 

The residual graph associated to the above solution is the following:  

III) The push-relabeled based algorithms are the ones which involves computing a residual network and looking for augmenting paths.

 

IV) The sum of the incoming flow of a vertex u has to be equal to the sum of the outgoing flow of u, except in the source and sink nodes 

Mark the alternative that list exactly the true statements:

a) only I and IV 

b) only I, II, and IV

c) only II and III

d) only III and IV

e) None of the above 

Original idea by: Levy Chaves

2022-124

Consider the two networks A and B above, where the numbers close to each edge represent its respective capacities of flow and π can only assume values greater or equal to 0:

Select the correct alternative below:

A) Independently of the value of π, the maximum flow of network A cannot be bigger than the value of the max flow of network B.

B) If the value of π is 0, the maximum flow of network A will be smaller than the value of the max flow of network B.

C) Depending on the value of π, network B may have a maximum flow bigger than network A.

D) Only if the value of π is bigger than 2 network A will have a bigger flow than network B.

E) None of the above.

Original idea by: Athyrson M. Ribeiro

2022-118

Consider the flow from S to T in the network below. Flow and capacity (F:C) are defined for each link. 

Which alternative represents possible values of flow/capacity for the variables x, y, w, z:

1. x=3, y=4, w=2, z=5
2. x=2, y=4, w=2, z=6
3. x=3, y=5, w=2, z=4
4. x=3, y=5, w=1, z=5
5. None of the above

Original Idea by: Iury Cleveston

2022-117

The push-relabel algorithm is one of many known algorithms used to find maximum flows. Consider the following statements about the push-relabel algorithm:

1. The push–relabel algorithm is one of the most efficient maximum flow algorithms. It allows the flow to exceed the edge's flow capacity, except from the source. It pushes as much flow as possible, and in the end, it saturates all edges from the source.
2. The push-relabel algorithm first steps are: Start with initial flow as zero, and then find augmenting paths and add them to the flow. When no more augmenting paths exist, return the resulting flow.
3. The push-relabel algorithm uses a labeling function to assign heights to the nodes, determining which ones should be selected for the push operation.
4. There is an implementation of the push-relabel algorithm that is called Edmonds-Karp algorithm. This implementation uses Breadth-First Search, which reduces the time complexity of the original algorithm.
5. Another differential from the push-relabel algorithm is that it also requires the construction of the level graph of the residual network.
   

Select the option that exactly list the correct statements:

1. I, II and III are correct.
2. I, III, IV and V are correct.
3. I and IV are correct.
4. I and III are correct.
5. None of the above.

Original idea by: Heitor Mattosinho