algoritmosemgrafos

The figure below shows a power transmission network. Nodes G1 and G2 are generators; C1 and C2 are consumers. The numbers on the edges are the maximum capacities (MW) of the transmission lines.      What is the maximum total flow that can be delivered from the generators (G1, G2) to the consumers (C1, C2)? Alternatives: A) 25 MW B) 30 MW C) 35 MW D) 40 MW E) None of the above Author: Giancarlo Maldonado Cárdenas

Consider the directed graph below: Applying the Kosaraju-Sharir algorithm, we wish to identify the strongly connected components (SCCs) of the graph. Regarding the steps and the result obtained, analyse the statements below: I. In the first execution of DFS, the completion times of each vertex are used to define the order of exploration in the transposed graph. II. The transposed graph is obtained simply by inverting all the edges of the original graph. III. Each tree in the search forest in the second execution of DFS corresponds to a strongly connected component. IV. The algorithm can identify cycles, but cannot isolate nodes that are not part of any cycle. Which statements are correct? A) I, II, and III only. B) I and IV only. C) II and III only. D) All are correct. E) None of the above. Author: Giancarlo Maldonado Cárdenas