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