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

 

2026-328

Consider two random graphs, G_a and G_b, where edges are created independently with probabilities p_a and p_b, respectively. Additionally, consider the following binomial degree distribution:

 

Consider N_a = 200 and  N_b = 100 

Evaluate the following statements:

I) The average degree <k> is higher in graph G_b.  

II) The variance of the degree distribution in G_b  is greater than in G_a .  

III) The expected number of edges in G_a is greater than in G_b.  

Select the correct alternative:

A) Only I is correct.  

B) Only I and II are correct.  

C) Only II and III are correct.  

D) I, II, and III are correct. 

E) None of the above.


Original idea by: Gabriel Ukstin Talasso

2026-327

 In a random network with \( N \gg 1 \) and average degree \( \langle k \rangle = 3 \), what is the expected fraction of nodes with degree 0 or 1?

1. \( 1 - e^{-3} \)
2. \( 4 e^{-3} \)
3. \( 3 e^{-3} \)
4. \( 2 e^{-3} \)
5. None of the above

Original idea by: Antonio De Cesare Del Nero

2026-326

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.

2026-325

You are analyzing a directed graph that represents a complex network of dependencies between software modules. You need to ensure the system is free of circular dependencies and find the minimum number of steps to reach a specific module from the source.

Based on the properties of Breadth-First Search (BFS) and Depth-First Search (DFS) presented in the course, which statement correctly identifies the best approach?

A) BFS should be used to find the minimum number of steps (length of a shortest path) because it provides parent links with a distance guarantee, while DFS is required to detect circular dependencies by identifying "back edges."

B) DFS should be used to find the shortest path because its "finishing times" represent the most efficient order, while BFS is the only tool capable of "edge classification" to find cycles.

C) In this directed graph, both BFS and DFS will naturally identify "forward" and "cross" edges, making them equally effective for topological sorting and cycle detection.

D) BFS is preferred for detecting cycles in undirected graphs because it lacks "forward edges," whereas DFS is preferred for shortest paths because it uses a stack to explore deep dependencies first.

Original idea by: Maria Luiza Ramos da Silva

2026-324

Consider the DFS time diagram below, which represents the starting and finishing times in a DFS call. Which of the graphs shown in the alternatives could produce it? 

a)                                                                      b)

             

c)                                                                       d) 

           

e) None of the above

Original idea by: Ingrid Barbosa

2026-323

Considering the following two undirected Graphs and three Degree Distributions:

Based on the previous figure, evaluate the following sentences as true (T) or false (F):

• Graph (1) matches the Degree Distribution X.
• Graph (2) matches the Degree Distribution Y.
• The maximum degree of Graph (1) is greater than that of Graph (2).
• The diameter of Graph (2) is greater than that of Graph (1).

Chose the correct alternative:

A) F, T, F, T

B) T, F, T, F

C) F, T, T, F

D) T, T, F, T

E) None of the above

 

Original idea by: Gabriela Caspa

2026-322

Given a graph where each node represents a student and two students are connected by a link if they have ever studied at the same school (not necessarily in the same class or year), which of the following statements is true?

a) A node with clustering coefficient equal to 1 implies that the student never changed schools.

b) A complete graph implies that there is just one school.

c) A student who never changed schools will have clustering coefficient equal to 1.

d) The number of connected components in the graph is necessarily equal to the number of schools.

e) None of the above.

Original idea by: Henrique Campos Padula

2026-321

Let \(G=(V,E)\) be a simple undirected graph, meaning that it has no self-loops (edges of the form \((v, v)\)) and no multiple edges between the same pair of vertices.

For such a graph we can define its degree sequence, as the sequence of its vertex degrees in nonincreasing order..

For example, the graph shown below has degree sequence

(3,1,1,1)

For each of the following statements, determine whether it is True (T) or False (F).

i) \( (2,2) \) is the degree sequence of several nonisomorphic graphs.
ii) \( (2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.
iii) \( (2,2,2,2,2,2) \) is the degree sequence of exactly one graph, up to isomorphism.

Alternatives

a) FTF
b) FTT
c) TFT
d) TTF
e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

2026-320

Figure 1(a) below shows a drawing of a network \(N\). Figures 1(b), 1(c), and 1(d) show the matrices \(A\), \(D\), and \(S\), respectively, and Figure 1(e) shows the vector \(k\). 

Regarding the figures above, consider the following six propositions:

1. For matrix \(A\), shown in Figure 1(b), entry \(a_{ij} = 1\) if and only if there is a link in network \(N\) connecting node \(i\) to node \(j\). Therefore, \(A\) is the adjacency matrix of network \(N\).
2. Matrix \(D\), shown in Figure 1(c), can be regarded as a matrix indicating second neighbors (nodes at distance two) of network \(N\), since entry \(d_{ij} \not= \infty\) if and only if nodes \(i\) and \(j\) are second neighbors.
3. Matrix \(D\), shown in Figure 1(c), can be regarded as a distance matrix of network \(N\), since if \(d_{ij} = \infty\) there is no path between nodes \(i\) and \(j\), and if \(d_{ij} \not= \infty\) then \(d_{ij}\) equals the length of a shortest path between nodes \(i\) and \(j\).
4. Matrix \(S\), shown in Figure 1(d), can be regarded as a matrix of second neighbors of network \(N\), since \(s_{ij} = 1\) if, and only if, nodes \(i\) and \(j\) are second neighbors.    
5. Vector \(k\) is the vector of the node degrees of network \(N\) and can be obtained multiplying matrix \(A\) by vector \( (1, 1, \ldots, 1) \)^T \) .  

Which alternative contains all the TRUE propositions?

(a) 1 and 3.

(b) 1, 2, and 3.

(c) 1, 2, and 5.

(d) 1, 3, 4, and 5.

(e) None of the above.

Original idea by: Joao Vianini

2026-319

Consider the four graphs below:

Which graph has the highest average clustering coefficient C, and what is its value?

A) Graph 1, with C = 0

B) Graph 4, with C = 0.47

C) Graph 2, with C = 0.50

D) Graph 3, with C = 0.10

E) None of the above

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

2026-318

Suppose a graph \(G\) has the following second power of the adjacency matrix:

$$ A^2 = \left( \begin{array}{cccc}1 & 0 & 1 & 1\\0 & 3 & 1 & 1\\1 & 1 & 2 & 1\\1 & 1 & 1 & 2 \end{array}\right) $$

Which one could be \(G\)?

a)

b)

c) 

d) 

e) None of the above

Original idea by: Leticia Marques

2026-317

 In an undirected network, suppose there are exactly 4 triangles and exactly 12 additional connected triplets, not belonging to triangles.  According to the definition of the global clustering coefficient, what is the value of ?

1. 1/2
2. 2/3
3. 3/4
4. 6/7
5. None of the above

Original idea by: Antonio De Cesare Del Nero

2026-316

Consider the following graph and the subsequent statements:

1. The graph is connected because the links (0, 1), (0, 2) and (0, 3) intersect with the links (4, 5), (4, 6) and (5, 6).

2. If we consider the components of this graph as projections of a bipartite graph, the parent bipartite graph could be:

3. The adjacency matrix of this graph can be rearranged and separated into two non-zero submatrices of size 4x4 and 3x3.

The correct statements are:

a) Just 3

b) 1 and 2

c) 1 and 3

d) 2 and 3

e) None of the above.

Original idea by: Rafael Brusiquesi Martins

2026-315

Using the Breath-First-Search (BFS) algorithm, how many nodes have a distance of 1, 2 and 3 from node A, respectively?

a) 2, 4, 3

b) 3, 3, 3

c) 3, 4, 2

d) 2, 3, 4

e) None of the above.

Original idea by: Matheus de Oliveira Saldanha

2026-314

Let \(A\) be the \(N \times N\) adjacency matrix of an undirected, unweighted network without self-loops. Let \( \textbf{1}\) be a column vector of \(N\) elements, all equal to 1, i.e., \( \textbf{1} = (1, 1, \ldots, 1)^T \). Let \(t(A)\) denote the trace of matrix \(A\), i.e., the sum of the elements on its main diagonal.

Which of the following expressions gives the number of connected triplets in the network?

1. \( ( \textbf{1}^T A^2 \textbf{1} ) / 2 \)
2. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 \)
3. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) - t(A^3) ) / 2 \)
4. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 - t(A^3)/6 \)
5. None of the above

Original idea by: Pedro Ferreira

2026-313

 Consider the following networks:

Choose the correct answer:

A) Only networks A, B, and D are bipartite.

B) All networks are bipartite.

C) Only networks A, B, and C are bipartite.

D) Only networks A and D are bipartite.

E) None of the above.

Original idea by: Melissa Araújo

2026-312

Look at the figures below, analyze the statements, and choose the right answer:

I- The graph in figure A is a multigraph and in figure B is a simple graph.

II- In a complete graph, known as a clique, all nodes are connected to each other.
III- The diameter of the graph in figure B is dmax= 4.

IV- The adjacency matrix of graph in figure B is:

1. I and II are correct
2. II, III and IV are correct
3. II and IV are correct
4. I, III, IV are correct
5. None of the above

Original idea by: Tássia Martins

2026-311

 Consider the following network.

Which of the following statements are true:

I. FECFAU and FEAGRI are the only nodes with the lowest degree.

II. The degree distribution shows that 60% of the nodes have degree 3.

III. The local clustering coefficient of IQ and IE is 1.

IV. The diameter of the graph is 4.

V. No links are bridges

a) I, II, and III.

b) III and V.

c) I, III, and IV.

d) II, IV, and V.

e) None of the above.

Original idea by: George Gigilas Junior