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