06.03.2026 | Graph Theory

Observe the graph below and choose the correct alternative.


Consider the following statements: 
I. There are two bridges and two strongly connected components.
II. Removing node A results in a graph with no strongly connected components.
III. Creating the link HE results in a new strongly connected component.
IV. Removing the link IA transforms the graph into a disconnected graph.

The alternative that represents the correct statements is:
a) Only statements I and II are correct.
b) Only statements II and IV are correct.
c) Only statements II, III, and IV are correct.
d) Only statements I, III, and IV are correct.
e) None of the above.


Original idea by: Yuri S. Costa

Comentários

  1. Joao Meidanis8 de março de 2026 às 12:21

    Nice question, but it can be a bit confusing, since the terms "bridge" and "disconnected" refer primordially to undirected graphs. For directed graphs, it would be clearer to redefine them, and clarify if you mean strong or weak connected components in the definitions.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

13.03.2026 | BFS

Imagem
Consider the following statements regarding a Breadth-First Search (BFS) traversal of the graph. Assume that whenever multiple neighbor nodes are available for expansion, they are selected in ascending numerical order : I. The BFS traversal path when starting from node 1 is: 2-4-6-3-7-9-10-5-8.  II. Nodes 5 and 8 are the furthest from node 1, just as node 1 is the furthest node when the search is initiated from either node 5 or 8. III. Adding an edge between nodes 9 and 8 alters the path when expanding from node 1, causing node 8 to be discovered before node 5. IV. Adding a new edge between nodes 2 and 7 makes no difference to the generated path when starting the expansion from node 1. The alternative that represents the correct statements is: a) Only statements I and II are correct. b) Only statements I, III, and IV are correct. c) Only statements II and IV are correct. d) Only statements IIII and IV are correct. e) None of the above. Original idea by: Yuri S. Costa
Leia mais

10.04.2026 | Network Flow

Imagem
 In the study of Network Flow, the Ford-Fulkerson algorithm relies on constructing a Residual Network $R_f$ from an original flow network $G$ and a valid flow $f$ . Below is the Residual Graph ( $R_f$ ) generated from an unknown flow network. Which of the following pairs of Original Network $G$ (left) and Flow $f$ (right) correctly generated the Residual Graph above? Pair I: Pair II: Pair III: Pair IV: The alternative that represents the correct statement is: a) Only pair II is correct. b) Only pairs I and III are correct. c) Only pairs II and IV are correct. d) Only pair I is correct. e) None of the above. Original idea by: Yuri S. Costa
Leia mais