Question 3 - Network Flow

Consider a flow network G=(V,E) with capacities c(e) and a flow f. 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?

a) 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.

b) 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.

c) 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.

d) The residual network is constructed only once at the beginning of the algorithm and remains fixed throughout the process, guaranteeing polynomial complexity.

e) None of the above.

 

Original idea by: Pedro Pereira

Question 2 - Kosaraju-Sharir's Algorithm

The Kosaraju–Sharir's algorithm is used to identify strongly connected components (SCCs) in directed graphs. It runs in O(V + E) time, since it performs two depth-first searches (DFS) and uses the transposed graph.

Consider the directed graph with vertices {0, 1, 2, 3, 4, 5, 6, 7} and edges:

(0 → 1), (1 → 2), (2 → 0), (2 → 3), (3 → 4), (4 → 5), (4 → 7), (4 → 6), (5 → 6), (6 → 7)

Regarding the application of the Kosaraju–Sharir's algorithm to this graph, select the correct alternative:

a) The algorithm finds four strongly connected components: {0,1,2}, {3}, {4,5,6} and {7}.

b) The algorithm finds three strongly connected components: {0,1,2}, {3} and {4,5,6,7}.

c) The algorithm cannot be applied to directed graphs, only to undirected graphs.

d) The algorithm finds eight strongly connected components, each vertex being isolated.

e) None of the above.

Original idea by: Pedro Pereira