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