Bianca was helping prepare the decorative flags for the booths at the São João festival, traditionally known as Festa Junina in Brazil. While cutting the flags, she removed the some portions, leaving only triangular shapes. This inspired her to relate the patterns to concepts from her Graph Algorithms course in her Master’s program in Computer Science. 

The figure below presents the decorative flags, which Bianca reimagined as two networks, N1​ and N2, composed of the same number of vertices but with different levels of connectivity. Based on the visual structure of the networks and the concepts of robustness in graphs, choose the correct alternative and help Bianca with her reasoning.



a) Network N1​ ​has the smallest value of the critical threshold fc because of its denser structure.

b) Among the two networks, N1​ requires the largest fraction of node removals to break apart, indicating the highest critical threshold fc.

c) Although network N2 has the smallest critical threshold fc, it is still the most resilient structure and the most prone to spreading failures.

d) The lower average connectivity of network N2 leads to a larger critical threshold fc.

e) None of the above.


Original idea by: Melissa Araújo.

Comentários

  1. Joao Meidanis16 de maio de 2026 às 06:01

    I feel that these considerations on f_c work best for large networks. For instance, the Molloy-Reed criterion is for networks with N going to infinity. For small networks such as the ones considered here the conclusions are not so straightforward. Therefore, I prefer to leave this question out.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Imagem
Consider the following networks: Choose the correct answer: A) Only the A, B and C graphs are bipartite. B) All the graphs are bipartite. C) Only the A, B and D graphs are bipartite. D) Only the A and D graphs are bipartite. E) None of the above. Original idea by: Melissa Araújo
Leia mais
Imagem
Consider the graph on the figure below. Determine the number of back edges, cross edges, and forward edges generated by the Depth-First Search (DFS) algorithm. Assume the algorithm visits neighboring vertices in ascending order. A) 2 back edges, 4 cross edges, and 2 forward edges.  B) 2 back edges, 5 cross edges, and 1 forward edge. C) 1 back edge, 4 cross edges, and 2 forward edges. D) 1 back edge, 5 cross edges, and 2 forward edges. E) None of the above. Original idea by: Melissa Araújo.
Leia mais
Imagem
Cynthya is a big fan of the band Suplaz, which rarely performs in Brazil. She just found out they’ll be at Rock in Rio and is thrilled. She is the manager of the Capanema (Pará) Suplaz fan group, so she decides to organize transportation to help as many fans from her city as possible attend the concert.  Since the trip is long, she sets up a system of shared rides and transfers: fans can travel between cities using different cars, vans, or buses, meeting at stops along the way. At each segment of the trip, there is a limit to how many people can be transported, depending on vehicle availability. Fans may switch vehicles at intermediate stops. The figure above represents this transportation system as a directed network. Capanema is the source (S) and Rock in Rio is the sink (T). The intermediate nodes (A, B, C, and D) represent transfer points, like hotels or meeting locations. Each edge has a capacity, indicating the maximum number of people that can travel along that segment. Usin...
Leia mais