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
Analyze the statements below, knowing that DFS and BFS algorithms start at node "a" and the adjacency lists are sorted in alphabetical order.
I. During the BFS execution, three nodes that are already visited are verified (thus not being visited again);
II. There is just one back edge in the graph;
III. If we remove edges cd and ef, the resulting graph is a bipartite graph;
IV. The DFS execution would restart twice in this graph, creating two different trees;
The correct statements are:
a) I and III
b) Only II
c) II and III
d) I, II and IV
e) None of the above
Original idea by: Giorgio Rossa
Consider a graph
, and the Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. Analyze the following statements:
I. In a DFS execution on a directed graph, the classification of edges as tree, forward, backward, and cross edges depends on the order in which vertices are explored.
II. In a BFS executed from a source vertex in an unweighted graph, the order in which vertices are discovered at the same level may vary depending on the order of edges in the adjacency list of the graph, but the minimum distance from each vertex to remains unchanged.
III. In directed graphs, a back edge detected during DFS indicates the presence of at least one cycle that includes the origin vertex of the edge.
IV. In undirected graphs, BFS can detect all cycles of length 3 (triangles), but it does not guarantee detection of larger cycles.
V. DFS guarantees that in a connected undirected graph, the tree generated contains exactly edges, independently of the presence of cycles.
Select the correct alternative:
A) Only I, II, and III are correct.
B) Only II, III, and IV are correct.
C) Only I, III, IV, and V are correct.
D) Only II, III, and V are correct.
E) None of the above.
Original idea by: Mateus de Padua Vicente
The Health Department of the imaginary region Scarlet is preparing contingency plans for a potential pandemic. To ensure efficient allocation of resources, they want to determine:
Which city would serve as the most effective distribution center for medication, minimizing its expected distance to the other cities, thus guaranteeing accessibility to the largest number of other cities in the shortest time.
Which city would serve as the most strategic location for establishing a blockade, in order to minimize the potential spread of infection to other cities within the network?
Considering the graph below, where each node represents a city and the only means of connection between them is via roads represented by the edges, which cities represent the best candidates for these roles?
Consider the adjacency matrices A and B below, where A represents an undirected network and B represents a directed network.
Choose the alternative whose networks generate matrices A and B, respectively.
A. 
B. 
C. 
D. 
E. None of the above
Original idea by: Jhessica Silva
Eight dogs are happily playing at Praça da Paz, Barão Geraldo. Each dog is a node, and each friendship (two dogs playing together) is an edge.
Considering the above undirected network of dog friendships, which of the following statements is correct?
A) The clustering coefficient of node Violeta is 0
B) Ginger is very social and her clustering coefficient is 0.5, participating in more than one triangle
C) The shortest path from Mindú to Violeta has length 4
D) The average degree of the nodes ⟨k⟩ is 2.375, and the degree distribution shows that three nodes have degree 1
E) None of the above
In a bomb defusing training, were each explosive is wired to another in different ways, the instructions given by the trainers include using Breadth-First-Search to defuse each bomb and leaving the main explosive to be defused last. Facing the following wired structure, which node should be the starting one in order to follow the instructions faithfully?
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...
