2025-261

Consider a directed graph \(G\) 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) None of the above.

Original idea by: Mateus de Padua Vicente

2025-260

A technical leader responsible for the software testing team intends to allocate a functional requirement to a team member who currently has no assigned tasks. For this assignment, the objective is to select a functional requirement that does not have strong dependencies on other requirements. Therefore, the leader chose to use the Kosaraju-Sharir algorithm to identify the Strongly Connected Components composed of only a single vertex.  Requirement dependencies are represented in the directed graph shown in the image below.

Which functional requirement was assigned to the team member for testing?

    A. FR01

    B. FR03

    C. FR05

    D. FR07

    E. None of the above

Original idea by: Jonas Henrique Ribeiro Paula

2025-259

Consider the following directed graph:

I. The shortest path from A to J has length 5, and this is the longest among all shortest paths in the graph.

II. The number of cycles in the graph is exactly half the number of its strongly connected components.

III. If each strongly connected component is collapsed into a single node, there will be two possible topological orderings of the graph.

IV. If node D and all its incident edges are removed, and a new edge from B to E is added, the resulting graph will form a single strongly connected component.

Which of the statements are correct?

A) I, II, and III

B) Only III

C) III and IV 

D) Only IV

E) None of the above

Original idea by: Jhonatan Cléto

2025-258

A fungal colony, whose hyphae form a network called the mycelium, started growing on a piece of bread left unattended. The colony started small, at an initial number of spores \(N = 5000\). It is known that, although the number of spores remains constant, this species creates hyphae (links) over time, so that at any point in time it looks like a random \(G(N,p)\) network, where \(p\) is given by the function below:

\( p(t) = t/10^{4}\)

where t is the time measured in days.

Given two different intervals:

• A day has passed
• Three days have passed\

Assign the correct alternatives with respect to attributes about the mycelium growth.

1. As one day passes, the network is subcritical, and by three days, it remains subcritical.
2. As one day passes, the network is subcritical, and by three days, it’s supercritical.
3. As one day passes, the network is critical, and by three days, it’s supercritical.
4. As one day passes, the network is already supercritical.
5. None of the above.

Original idea by: Alexandre Petrachini

2025-257

\(G_1(N,p_1)\) and \(G_2(N,p_2)\) are two random networks with the same number of nodes \(N\), but different link probabilities, with \(p_1 > p_2\).

Which of the following statements is correct?

1. \(G_1\) will have a lower clustering coefficient than \(G_2\).
2. \(G_2\) will have a larger average degree than \(G_1\).
3. Both \(G_1\) and \(G_2\) must have the same degree distribution, since they share the same number of nodes \(N\).
4. \(G_1\) is more likely to contain a giant component than \(G_2\).
5. None of the above.

Original idea by: Gabriel Sato 

2025-256

Given the following plot for the theoretical binomial distribution of degrees in a random graph created with 250 nodes,

what was the probability (rounded to 2 decimal places) of edge creation used?

A) 0.01

B) 0.05

C) 0.10

D) 0.20

E) None of the above.

Original idea by: João Medrado Gondim

2025-255

A BFS was performed on an unknown graph, producing the following visitation order:

a-c-d-b-f-g-e-h

There are four candidate graphs:

I)

II)

III)

IV) 

Assuming that neighbors are always visited in ascending order, which of the graphs are valid candidates for the original graph?

a) I and II

b) I and III

c) II and IV

d) III and IV

e) None of the above

Original idea by: Pedro Zaffalon da Silva