2022-163

Consider a network containing \(N\) nodes and with a minimum degree \(k_{min}\). If the degree distribution \(p_k\) follows a power law \(p_k \sim k^{-\gamma}\), where the exponent \(\gamma\) is the degree exponent, what is correct to affirm:

A. The average distance \(\langle d \rangle\) between two nodes is proportional to \(\ln N\) for \(2<\gamma\leq 3\).

B. The first moment \(\langle k \rangle\) diverges for \(2<\gamma\leq 3\).

C. The second moment \(\langle k^2 \rangle\) diverges for \(\gamma > 3\).

D. The expected size of the largest hub is \(k_{min}N^{\frac{1}{\gamma - 1}}\).

E. None of the above.

Original idea by: Marcelo Silva

2022-162

Consider two random networks A and B. Network A has 17 nodes and probability p = 1/4 of an edge existing between any two nodes.  Network B has 31 nodes and probability p = 1/5 of an edge existing between any two nodes. The average degree of networks A and B respectively will be?

1.  2 and  4
   
2.  8 and 10
3.  6 and  8
4.  4 and  6
5. None of the above

Original idea by: Meer Muhammad Khan

2022-161

Consider a random network \( X \) with \( N \) nodes connected to each other with probability \( p = 0.2 \), and a random network \( Y \) also with \( N \) nodes but connected to each other with probability \( p = 0.4 \). Choose the correct alternative.

1. \( \langle k_X \rangle \lt \langle k_Y \rangle \)
2. \( \langle L_X \rangle = 2 \langle L_Y \rangle \)
3. \( \langle d_X \rangle \lt \langle d_Y \rangle \)
4. \( \langle C_X \rangle = 2 \langle C_Y \rangle \)
5. None of the above

Original idea by: Matheus Fernandes Sarmento

2022-160

Consider a random network with average degree equal to 1.05 and \( 10 ^9 \) nodes. Let \( N_G \) denote the expected magnitude of this network's largest cluster (also known as giant component). Which alternative corresponds to the base 10 logarithm of \( N_G \) within 1% ?

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

Original idea by: Gabriel Oliveira

2022-159

Given the following oriented graph and applying two BFSs, one starting from node A (BFS-A), and the other starting at D (BFS-D), which of the following statements are true?


I.   BFS-A visits node D.
II.  The number of visited nodes in BFS-A is 5
III. BFS-D gets to visit all nodes in the graph.
IV. Deleting the red links reduces the number of visited nodes in BFS-D.

 

    A. Only II

    B. II and IV

    C. II, III and IV

    D. III and IV

    E. None of the above

    Original idea by: Victor Sotelo

2022-158

Concerning the Breadth First Search (BFS) algorithm with a queue, observe the oriented graph below, and assume that the adjacency lists are arranged in decreasing order.

Suppose you start a BFS in this graph from node 3.  Select the option representing the order of node numbers loaded into the queue during this operation.

1. 3 – 4 – 6 – 5 – 7 – 8 – 2 – 1 – 10
2. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1
3. 3 – 4 – 5 – 6 – 2 – 8 – 7 – 10 – 1
4. 3 – 6 – 5 – 4 – 8 – 7 – 2 – 1 – 10
5. None of the above.

Original idea by: Rubens de Castro Pereira

2022-157

Considering the following graph.

Which one of the following is a possible order for visiting the nodes using BFS?

1. QMNPRO
2. NQMPOR
3. MNOPQR
4. QMNPOR
5. None of the above

Original idea by: Rodrigo Bifulco

2022-156

Given the directed and unweighted graph below, and supposing that we start in node 1:

Which of the following items gives the information about the Furthest Node from 1 and one of the Shortest Paths to the furthest Node?

1. Furthest Node: 8 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 8 \)
2. Furthest Node: 9 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 6 \rightarrow 7 \rightarrow 9 \)
3. Furthest Node: 8 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 6 \rightarrow 7 \rightarrow 8 \)
4. Furthest Node: 9 and Shortest Path: \( 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 8 \rightarrow 9 \)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-155

The Breadth First Search (BFS) algorithm has been implemented using the queue. Which of the following is a best possible order of visiting the nodes in the graph below?

A. ABCDEF

B. ABCFDE

C. ABCFED 

D. EDFCBA

E. None of the above

Original idea by: Muhammad Idrees

2022-154

Given the unoriented graph below, indicate the correct distances from node 1 to each node different from 1, in the numerical ascending order of nodes. Tip: you may use the BFS algorithm.

 

 

 

 

 

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

Original idea by: André Nóbrega

2022-153

Given the following oriented graph, which of the statement are true?

I.   Removing any node affects the strong connectivity status (strongly connected or not)

II.  The graph is strongly connected.

III. The length of the shortest path from A to C is 4

IV.  There exist exactly 4 cycles in the graph.

 

 

    A. Only I

    B. II and IV

    C. I and II

    D. only IV

    E. None of the above

Original idea by: Victor Sotelo

2022-152

Consider the following graph. If there is a decision between multiple neighbor nodes in the Depth-First Search (DFS) or Breadth First-Search (BFS) algorithms, select the node with the smallest number.

In what order will the nodes be visited in both DFS and BFS algorithms starting at node 1?

1. DFS: 1 – 2 – 3 – 7 – 6 – 5 – 8 – 4  and  BFS: 1 – 2 – 4 – 5 – 3 – 7 – 8 – 6.
2. DFS: 1 – 2 – 3 – 5 – 8 – 7 – 6 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
3. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 6 – 8.
4. DFS: 1 – 2 – 3 – 5 – 8 – 6 – 7 – 4  and  BFS: 1 – 2 – 4 – 3 – 5 – 7 – 8 – 6.
5. None of the above.

Original idea by: Rubens de Castro Pereira

2022-151

Pedro has been given several tasks to do. But instead of a list with the order of the tasks, his supervisor gave him a graph where edges that go from node A to B mean that task B depends on task A. Unfortunately, Pedro does not know how to use this information from the graph, so he doesn't know which tasks to do first. The graph his supervisor provided was:

As a specialist in graphs, you were chosen to help Pedro with ordering the tasks he needs to do. His supervisor said to him to always prioritize the task with the smallest label when there is a choice. Knowing the constraints, which order should Pedro follow?

1. 1, 2, 3, 4, 7, 6, 9, 10, 8, 5
2. 1, 5, 2, 3, 4, 7, 6, 8, 9, 10
3. 1, 5, 2, 6, 4, 8, 9, 7, 10, 3
4. 1, 2, 6, 3, 4, 7, 9, 10, 8, 5
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

2022-150

How many topological orderings exist in  the graph given below?

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

Original idea by: Meer Muhammad Khan

2022-149

Given the following directed graph, if DFS is started from vertex 0 for an implementation in which the adjacency lists are in sorted order, then what is correct to affirm regarding edge classifications:

A. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge

B. {b, e, d, i, j, c} are tree-edges; 

     {g} is a forward-edge; 

     {a} is a back-edge; 

     {h} is a cross-edge;

C. {a, b, c, g} are tree-edges; 

    {d, h} are forward-edges;

    {e, f} are back-edges;

    {i} is a cross-edge;

D. {a, b, c, d} are tree-edges; 

    {g, h} are forward-edges;

    {e, i} are back-edges;

    {f} is a cross-edge

E. None of the above

Original idea by: Marcelo Silva

2022-148

Given the network of Figure 1, which alternative does not describe a possible topological sorting of this graph?

Fig. 1. Network.

1. A, C, G, E, D, H, B, F
2. E, A, G, C, B, D, H, F
3. A, B, C, D, E, G, H, F
4. G, A, C, E, B, H, D, F
5. None of the above.

Original idea by: Gabriel Oliveira

2022-147

Consider the Active Time Diagram defined below. The rows, \( a \) to \( e \), represent the nodes of a network. The columns, 1 to 10, represent the star and ending times of the nodes during a given DFS Algorithm, which starts at node \( a \) and proceeds through the network. So, the horizontal bar at row \( a \) indicates that node \( a \) has starting time 1 and ending time 10, delimiting the time it is active, and so on for the others.

Based on this diagram, we are able to infer some information on Edge Classification, as follows:

1. Edges \( d \rightarrow c \) and \( e \rightarrow d \) are cross-edges.
2. Edges \( a \rightarrow c \) and \( a \rightarrow e \) are forward-edges.
3. Edge \( c \rightarrow a \) is a backward-edge.

Given the above statements, which of them are true:

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

Original idea by: Fábio Assunção.

2022-146

A truck driver from a food supply company has to visit several cities to make deliveries. However, he must visit some cities before others, in order to pick up important items. These precedence requirements are shown as the edges in the graph below. Whci alternative shows a topological order of cities?

 

 

 

 

1. São José do Rio Preto, Ribeirão Preto, Araçatuba, Bauru, Campinas, São Carlos, Andradina, Mococa
   
2. São Carlos, Andradina, Araçatuba, Bauru, Campinas, Mococa, São José do Rio Preto, Ribeirão Preto
3. São José do Rio Preto, Ribeirão Preto, São Carlos, Andradina, Araçatuba, Bauru, Campinas, Mococa
4. Andradina, São José do Rio Preto, Araçatuba, Bauru, São Carlos, Ribeirão Preto, Mococa, Campinas
5. None of the above.

Original idea by: André Nóbrega

2022-145

Considering the graph given below, the number of connected triplets and triangles are:

1. 14 connected triplets and 0 triangles
2. 15 connected triplets and 1 triangle
3. 16 connected triplets and 2 triangles
4. 17 connected triplets and 3 triangles
5. None of the above

Original idea by: Meer Muhammad Khan

2022-144

Consider the Network corresponding to the Adjacency Matrix A defined below. 

A=⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢0101000101100001000001100011000001000011010001010⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

Build the Network using nodes 1 to 7. Then, for each node ni, calculate its respective Clustering Coefficient Ci, and then, use them to calculate the Average Clustering Coefficient, ⟨C⟩, of the entire Network. Once the calculation is done, state which of the options listed below represents the correct value of ⟨C⟩:

1. ~ 0.38.
2. ~ 0.43.
3. ~ 0.48.
4. ~ 0.51.
5. None of the above.

Original idea by: Fábio Assunção.