2023-202

Consider the following statements regarding the graph below, where a DFS algorithm was run, starting at A.  Assume the adjacency lists are in alphabetical order. 

 

 

 

I. Edge 4 is a forward edge.

II. Edge 11 is the only cross edge.

III. There are 8 tree edges.

 

Which of the alternatives below is correct?

(A)  Only I and II are correct.

(B) Only II and III are correct.

(C) Only I is correct.

(D) Only III is correct.

(E) None of the above. 

 

Original idea by: Raysa Masson Benatti 

2023-201

The figure below is a dependency graph representing the course prerequisites in a school. The courses are the nodes, and the requirement relationships are defined by direct links from a course to its prerequisites to be enrolled.

For example, in the figure below:

• Course D has course A as a prerequisite; and
• Course E has courses A and B as prerequisites.

Considering the figure above, mark the following sentences as true (T) or false (F):

• The only node with the highest degree is node M;
• Nodes A, B, and C do not have prerequisites;
• Course G is a prerequisite for course H;
• The incoming degree for course O is 2;
• The outgoing degree for course H is 2;

The correct option matching the sentences is:

a) T-T-F-F-T

b) F-T-F-F-T

c) F-F-T-T-T

d) T-T-F-T-F

e) None of above

Original idea by: Leonardo H. de Braz

2023-200

Analyse the following graph:

Choose the true statement:

A) Both node D and node A have the same clustering coefficient.

B) Node E has the highest clustering coefficient.

C) This graph can be classified as a disconnected graph since not all nodes connect with each other.

D) Node F currently has a clustering coefficient of zero. However, if we establish a connection between node F and node A, its clustering coefficient would be the highest in the graph.

E) None of above

Original idea by: João Marcos

2023-199

The following network represents computers and their connections in a distributed system. The communication between computers flows through the links in any direction.

The system started presenting performance issues.  After some investigation, the cause was attributed to node communication bottlenecks. By looking at the network, which one of the options presents both a reasonable bottleneck cause and a reasonable solution to it?

1. Node 6 has a high clustering coefficient, which indicates a network vulnerability for failures. By removing node 6, the system communication should improve.
2. Node 4 may be overloaded since many nodes depend on it to communicate with each other. By adding link (3,4), performance should improve.
3. Link (3,5) may be overloaded, since it is a bridge and if removed, two connected components are created. By adding link (2,6), performance should improve.
4. The network diameter is 5, as witnessed by the path {(2,1), (1,3), (3,5), (5,7), (7,8)}, which is too high. By adding link (2,8), performance should improve.
5. None of the above

Original idea by: Christian Konishi

2023-198

Consider the Following Applications of the BFS Algorithm starting at the Orange Node:

Which examples are applying BFS the wrong way:

A) B and C

B) B and D

C) A and D

D) Only C

E) None of the above

Original idea by: Arthur Hendricks.

2023-197

Considering the four directed graphs in the following figure:

Which of them are strongly connected and have a diameter 4:

1. III and IV
2. only III
3. only II
4. I and II
5. none of above

Original idea by: Anderson Nogueira Cotrim

2023-196

 Given the following projections of a bipartite network :

Which of the options below provides a possible network that generated these projections? 

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

Original idea by: Hitalo Cesar