2026-335

Maria studies at UNICAMP and is taking a Graph Algorithms class. Driven by curiosity, she applied what she learned in class to a network generated from her classmates' profiles on the social media platform Z. The nodes of the network are Maria's classmates and an outgoing edge indicates following someone, while an incoming edge indicates being followed by someone. 

She wanted to identify specific clans and see if there were any isolated classmates. Her goal was to bring those people into a community to ensure no one feels alone in class. Could you help her identify the number of communities and isolated profiles in this network?

Maria defines a clan as any group of classmates forming a Strongly Connected Component (SCC) of two or more people (nodes). Any classmate who belongs to an SCC of only one person (node) is considered an isolated profile.

a) There are 3 communities and 4 isolated profiles.

b) There are 2 communities and 4 isolate profiles.

c) There are 1 community and 6 isolated profiles.

d) There are 1 community and 4 isolated profiles.

e) None of the above.

Original idea by: Melissa Araújo

2026-334

In a directed graph define two functions:

\( f(u, v) \): there exists a directed path from \(u\) to \(v\) .

\( scc(u) \) : Returns the SCC containing node \(u\).

For each of the following logical statements, determine whether it is True or False for any arbitrary directed graph:

1. \( scc(u) = scc(v) \Longrightarrow f(u,v) \)
2. \( (f(u,v) \) and \( f(v,u)) \Longleftrightarrow scc(u) = scc(v) \)
3. \( f(u,v) \Longrightarrow scc(u) = scc(v) \)
4. \( (f(u,v) \) and \( f(v,w)) \Longrightarrow f(u,w) \)

---

Alternatives

a) TTFT
b) TFFF
c) TFFT
d) TTTT
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-333

A delivery driver is working in a neighborhood where the streets are one-way. He serves one restaurant (R1) and has received 6 delivery requests (C1 to C6) from different customers in that neighborhood. The graph below represents the routes, respecting the directions of the streets. 

The driver will try and satisfy as many requests as possible, but must return to the restaurant after serving customers to receive his payment, without violating the street directions. After picking up the orders at the restaurant, which of the following alternatives is correct? 

(A) All customers would receive their orders.

(B) Only customers C1 and C3 would receive their orders.

(C) Customers C5 and C6 would not receive their orders.

(D) Only customer C1 and C2 would receive their order.

(E) None of the alternatives.

Original idea by: Ingrid Barbosa

2026-332

As the average degree \( \langle k \rangle \) of an Erdős-Rényi random network increases, the network's topology undergoes distinct phases of evolution. Which of the following statements accurately characterizes the network exactly at its critical point (\( \langle k \rangle = 1 \) )?

A) The size of the largest component scales as \( N^{2/3} \), containing a vanishing fraction of all nodes, and the cluster size distribution follows a power law. 

B) The network lacks a giant component, and the size of the largest cluster scales logarithmically with the total number of nodes. 

C) A giant component emerges that contains a finite fraction of the network's nodes, and the distribution of cluster sizes is exponential. 

D) The giant component absorbs all isolated nodes and clusters, rendering the network fully connected. 

E) None of the above.

Original idea by: João Vianini

2026-331

Regarding the models G(N, p) and G(N, L), choose the correct alternative:

A) Choosing p = 2L/N(N-1) will guarantee that the graphs generated by G(N, p) and G(N, L) have the same number of edges.

B) If N1 > N2 and L > 0, any graph generated by G(N1, p) will have more edges than any graph generated by G(N2, L).

C) For N1 > N2, and p1 > 0,  G(N1, p1) can generate graphs with an impossible number of edges for any graph generated by G(N2, p2) to reach, regardless of the value of p2.

D) The degree distribution of graphs generated by G(N, p) follow a power-law, as very often real-world graphs do.

E) None of the above.

Original idea by: João Pedro Carolino Morais

2026-330

Consider graphs with \(N = 4\) nodes. Below are three sample outcomes of \( G(N, p) \) at different values of \( p \). Dashed lines show absent edges.

  

Which graph is in the supercritical regime?

(A) All three are supercritical since every node has at least one neighbor

(B) Graph A, because it has at least one edge and \( \langle k\rangle = 0.3 > 0 \)

(C) Graph B, because \(\langle k\rangle = 1 \) satisfies the condition for the giant component

(D) Graph C, because \( \langle k\rangle = 2.4 > 1 \) and \( p = 0.8 > p_c = 1/3 \)

(E) None of the above.

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

2026-329

A company is looking for people that have really close acquaintances with its three interviewers. Therefore, candidates whose average length to each interviewer are closer to 1 will have the most chances to get the job.

Given the network of acquaintances of each of the following three applicants, indicate which of the following statements are true (T) or False (F).

Robert:

John:

Casey:

1. Casey has the most chances of getting the job.
2. For Robert’s network of aquaintances: If the clustering coeficient of Taylor were higher while maintaining the same degree, then Robert would have more chances of being hired.
3. The chances of Casey getting the job does not depends on knowing Micah, Mary or Harry.
4. John has the least chances of getting the job.

1. F F T T
2. T T T F
3. T F T F
4. T F F F
5. None of the above

Original idea by: Giuliano Macedo