MO412 - Mateus de Padua Vicente

Consider the flow network below, with vertices  V = { s , a , b , t } , source  s , and sink  t . The edge capacities are given as: ( s , a ) = 10 ,  ( s , b ) = 5 ,  ( a , b ) = 15 ,  ( a , t ) = 10 ,  ( b , t ) = 10 A student applies the Ford-Fulkerson algorithm, choosing augmenting paths in the order they are found by DFS, without using BFS or any other fixed rule. After a few iterations, the student notices that the total flow found is 15, but there still exists an augmenting path in the residual graph. What does this example illustrate about the Ford-Fulkerson method? A)  This behavior only occurs if there are cycles in the graph, which is not the case here . B) The Ford-Fulkerson algorithm may stop before the optimum if the choice of augmenting paths is not made carefully. C) The choice of augmenting paths may affect the number of iterations and efficiency, but the algorithm still finds the maximum flow in the end. D)  The Ford-Fulkerso...

Consider a directed graph  G = ( V , E )  and the Kosaraju-Sharir's algorithm for finding strongly connected components (SCCs). Analyze the following statements: I.   The SCC decomposition of a directed graph is unique, but the particular order in which SCCs are discovered by Kosaraju’s algorithm may depend on the order of adjacency lists. II.   If a directed graph has no back edges in a DFS traversal, then each vertex forms a distinct SCC. III.  If  G  is strongly connected, then the second DFS in Kosaraju’s algorithm produces a single tree covering all vertices, regardless of the order of exploration. IV.   The order of vertices given by decreasing finishing times of the first DFS guarantees that the second DFS on the transposed graph  G T  discovers one SCC at a time. Select the correct alternative: A) Only I and II are correct. B) Only I and IV are correct. C) Only I, II and IV are correct. D) Only I, III and IV are correct. E) ...