2024-245

The Kosaraju-Sharir's algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. Which of the following alternatives correctly describes the main phases of the algorithm?

 

A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times.

B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS.

C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs.

D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process.

E - None of the above

Original idea by: Vanessa Oliveira Alves

2024-244

The goal of Kosaraju-Sharir's algorithm is to find all strongly connected components (SCCs) of a given input graph. Please take into consideration the directed graph provided below and select the appropriate alternative about the decomposition of the graph into SCCs using this algorithm.

A. Starting from A and using alphabetical order to apply the first DFS, node G has minimum (equal to 4) finishing time. 

B. Starting from A and using alphabetical order to apply the first DFS, node A has maximum (equal to 10) finishing time.

C. Each node of the graph is a strongly connected component.

D. {A, B, C, G, F}, {D}, and{E} are strongly connected components of the graph.

E. None of the above.

Original idea by: Karla Florentino

2024-243

In the evolving network model that includes the concept of fitness, how does a node's fitness influence its ability to gain new connections?

a) Fitness gives all nodes an equal chance to receive new connections, eliminating the advantage of high-degree nodes.

b) Nodes with higher fitness are more likely to receive new connections, even if they currently have a low number of links.

c) Fitness reduces the effect of preferential attachment, favoring nodes with fewer connections.

d) Fitnes only affects the removal of existing links, not the formation of new ones.

e) None of the above.

Original Idea by Sergio Sanchez

2024-242

In the Evolving Networks chapter of Barabasi's book, Network Science, many models for network evolution are presented. For most of these models, which of the following concepts is the starting point to derive degree probability distributions and other characteristics of the networks?

A) Clustering coefficient

B) Preferential attachment

C) Network robustness

D) Shortest path length

E) None of the above


Original idea by: João Augusto Ferreira de Moura