In the study of Network Flow, the Ford-Fulkerson algorithm relies on constructing a Residual Network
Which of the following pairs of Original Network
Pair I:
The alternative that contains a correct statement is:
Original idea by: Yuri S. Costa
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.
Original idea by: Tássia Martins
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.
.png)
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
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.
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
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
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
Maria studies at UNICAMP and is taking a Graph Algorithms class. Driven by curiosity, she applied what she learned in class to a network generated from her classmates' profiles on the social media platform Z. The nodes of the network are Maria's classmates and an outgoing edge indicates following someone, while an incoming edge indicates being followed by someone.
She wanted to identify specific clans and see if there were any isolated classmates. Her goal was to bring those people into a community to ensure no one feels alone in class. Could you help her identify the number of communities and isolated profiles in this network?
Maria defines a clan as any group of classmates forming a Strongly Connected Component (SCC) of two or more people (nodes). Any classmate who belongs to an SCC of only one person (node) is considered an isolated profile.
a) There are 3 communities and 4 isolated profiles.
b) There are 2 communities and 4 isolate profiles.
c) There are 1 community and 6 isolated profiles.
d) There are 1 community and 4 isolated profiles.
e) None of the above.
Original idea by: Melissa Araújo
In the study of Network Flow, the Ford-Fulkerson algorithm relies on constructing a Residual Network from an original flow network ...
