2025-310

Which of the following alternatives contains a graph with only one Strongly Connected Component (SCC)? 

a)

b)

c) 

d)

 

e) None of the above


Original idea by: Pedro Zaffalon da Silva

2025-309

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 → 6), (5 → 6), (6 → 7), (7 → 4)

Regarding the application of the Kosaraju–Sharir's algorithm to this graph, select the correct alternative:

a) The algorithm finds three strongly connected components: {0,1,2}, {3} and {4,5,6,7}.

b) The algorithm finds four strongly connected components: {0,1,2}, {3}, {4,5,6} and {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

2025-308

Consider a pathogen spreading on a highly heterogeneous contact network whose degree distribution follows a power law with exponent between 2 and 3.  Based on network epidemic theory and immunization strategies, which of the statements below is correct ?

A) In networks of this type, the epidemic threshold is positive. Therefore, random immunization is sufficient to stop the epidemic if at least 30% of the population is vaccinated.

B) Strategies that immunize the acquaintances of randomly selected individuals tend to target high-degree nodes, increasing the epidemic threshold.

C) The strategy of immunizing acquaintances of random individuals does not improve epidemic control in real networks, because there is no correlation between the degree of a node and the degree of its neighbors.

D) For networks with diverging second moment in their degree distribution, SI and SIS models have the same epidemic threshold, since hubs do not influence their dynamics.

E) None of the above.

 Original idea by: Pedro Zaffalon da Silva