2026-346

Consider a "Feasibility Matrix" \(M\) for all \(n, m \geq 1\), where an entry \(M_{n,m}\) is equal to 1 if a planar layout for the graph \(K_{n,m}\) is possible, and equal to 0 otherwise. Which of the following statements is true?

a) \(M_{n,m} = 0\) for all cases where \(n + m > 5\).

b) \(M_{2,m} = 1\) for all \(m \geq 1\).

c) The graph \(K_{3,3}\) is planar because it is possible to draw it in a 2D plane without any edges intersecting.

d) Every graph \(K_{n,m}\) is planar as long as \(n \neq m\).

e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-345

The administration of a major university plans to create paths connecting all restaurants in one of its campuses, to optimize pedestrian mobility. Due to environmental restrictions, tunnels are forbidden, and no path can cross another path. Considering the campus map below, where the red dots represent restaurants, choose the correct alternative:

a) The project would be feasible if the restaurants were divided into 2 groups of 4, with only one path connecting the groups.

b) The project would only be feasible if two of the restaurants were not directly connected to the others.

c) The project is feasible, since it is possible to create paths connecting all 8 restaurants pairwise, without crossing.

d) There is no way that the project would be feasible.

e) None of the above.

Original idea by: Ingrid Barbosa

2026-344

In a Barabási-Albert model with m = 2, node A is added at time tA= 1 and node B at time tB = 4, as illustrated in the Figure. Here tA and tB are the birth times ti of each node. What is the ratio kA(100) / kB(100)?

1. 1/2
2. 1
3. 4
4. 10
5. None of the above

Original idea by: Gustavo P. C. P. da Luz

2026-343

Consider a network that follows the Barabási-Albert model with \(m_0 = m = 2\). A node \(i\) joined the network at time \(t_i = 375\) and has degree \(k_i(t) = 40\) at the current time step. What is the expected diameter of this network now? Round to two decimal places.

1. \(\langle D \rangle \approx 4.20\)
2. \(\langle D \rangle \approx 4.81\)
3. \(\langle D \rangle \approx 2.80\)
4. \(\langle D \rangle \approx 3.81\)
5. None of the above

Original idea by: Carlos Trindade

2026-342

A secret organization suspects that some gang members form closed communication groups, that is, groups in which any member can send or receive messages from other members of the group, passing only through members of that group. To understand the communication traffic between these members, the organization created the following graph.

What are the closed communication groups of the gang members?

A) {Michael, Sophie, Daniel, Olivie, Lucas, Emma, ​​Ryan}, {Chloe, Ethan}

B) {Michael, Sophie, Daniel}, {Olivie, Lucas}, {Emma, ​​Ryan, Chloe}, {Ethan}

C) {Chloe}, {Ethan}, {Michael, Sophie, Daniel, Olivie, Lucas}, {Emma, ​​Ryan}

D) {Michael, Sophie, Daniel, Olivie}, {Lucas, Emma, ​​Ryan}, {Chloe}, {Ethan}

E) None of the above

Original idea by:  Angelica Santos

2026-341

 In the study of Network Flow, the Ford-Fulkerson algorithm relies on constructing a Residual Network  from an original flow network  and a valid flow . Below is the Residual Graph () generated from an unknown flow network.

Which of the following pairs of Original Network  (left) and Flow  (right) correctly generated the Residual Graph above?

Pair I:

Pair II:

Pair III:

Pair IV:

The alternative that contains a correct statement is:

1. Only pair II is correct.
2. Only pairs I and III are correct.
3. Only pair I is correct.
4. Only pairs II and IV are correct.
5. None of the above.

Original idea by: Yuri S. Costa

2026-340

During a peak usage period following a power outage, the network of a community center began operating using packet switching, where data is divided into small packets and transmitted across the network, and bandwidth is provided on demand.

The infrastructure is composed of devices interconnected by links with limited capacities. Each link has a maximum transmission capacity in (MB/s), representing how much data can be transmitted. The main objective of the system is to maximize the total flow of data (packets) sent from S to T.

Since packets can follow different paths to reach the destination, the network can be modeled as a directed graph. To ensure the best possible performance, we aim to determine the maximum flow of packets that can be transmitted from the source to the destination.  A schematic drawing of the community center's network with capacities is given below.

Which of the following alternatives represents a maximum flow of data sent from S to T?

a)



b) 

  


c) 

d)



e) None of the above.

Original idea by: Tássia Martins