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

Question 1 - DFS and BFS

Tomás is a hungry cat who has been trying for several days to catch Jairo, a clever and elusive mouse. It happens that, in order to reach his burrow, Mouse Jairo can only traverse the path (directed graph in the image below) using the DFS algorithm, while Tomás can only follow the path using the BFS algorithm. Based on your knowledge of graph search algorithms, answer whether Jairo will manage to escape from Tomás or if he will end up becoming his lunch:

Suppose we always choose first the letter closest to the beginning of the alphabet.

a) Jairo will reach the burrow before Tomás and escape.

b) Tomás will reach Jairo’s burrow before him and devour him.

c) Jairo will not be able to find his burrow.

d) Tomás will not be able to find Jairo’s burrow.

e) None of the above.

Original idea by: Pedro Pereira