2021-025

Consider a scale-free network that has \( N = 10^7 \) nodes, each of them connected to at least one node, and with at least one leaf. If the degree exponent is \( \gamma = 2.5 \), what is the maximum expected degree of this network? Round the result to the nearest integer.

1. \( k_{max} = 75 \)
2. \( k_{max} = 630 \)
3. \( k_{max} = 3162 \)
4. \( k_{max} = 46415\)
5. None of the above.

Original idea by: Bruno Almêda

2021-024

 Choose the incorrect alternative about scale-free networks and their properties.

1. Scale-free networks have a large quantity of small degree nodes.
2. For large node degree \( k \), the power law lays below the Poisson curve.
3. Scale-free networks are networks whose degree distribution asymptotically follows a power law.
4. Many real networks such as the citation and email networks, are scale-free.
5. None of the above. 

Original idea by: Adolfo Aires Schneider

2021-023

Consider a Random Network with \( N = 100 \) nodes and probability \( p = 0.4 \) that two nodes are connected. The values of \( \langle L \rangle \) (expected number of links in this random network) and \( \langle k \rangle \) (average degree for this random network), are, respectively:

1. 1980 and 40
2. 2000 and 39.6
3. 2000 and 40
4. 1980 and 39.6
5. None of the above

Original idea by Angelica Oliveira

2021-022

Given a Random Network with \( N = 10000 \) nodes, and a probability \( p = 0.01 \) that a node pair is connected, what is the probability that a given node \( n \) will have exactly \( k = 100 \) links?

(Obs. Round off the result to 2 decimal places)

1. 0.01
2. 0.02
3. 0.04
4. 0.08
5. None of the above

Original idea by: José Nascimento

2021-021

In a graph, a "tree edge" is an edge that is present in the tree obtained after performing DFS on the graph. Suppose that \(k\) tree edges resulted from a depth-first traversal of an \(n\)-vertex, undirected graph. The number of the connected components in the graph can be calculated as:

1. \( k-1 \)
2. \( k \)
3. \( n-k \)
4. \( n-k+1 \)
5. None of the above

Original idea by: Soroor Salavati

2021-020

Consider the following graph:

Which alternative corresponds to a possible DFS order of node visits?

a. A, B, D, F, E, C, G 

b. A, B, C, D, E, F

c. A, C, D, B, E, F

d. G, C, A, B, C, D, F

e. None of the above

 

Original idea by: Wandersom Moura

2021-019

Which of the formulas below computes the average degree of an undirected network, where \( N \) is the number of nodes in the network,  \( k_i \) is the degree of node \( i \), \( N_k \) is the number of degree-\(k\) nodes, and \( A \) is the adjacency matrix:

1. $$ \sum_{j=1}^N A_{j,i} $$
2. $$ \dfrac{1}{2} \sum_{i=1}^N k_i $$
3. $$ \dfrac{1}{N} \sum_{i=1}^N k_i $$
4. $$ \dfrac{N_k}{N} $$
5. None of the above

Original idea by Mauricio Schiezaro

2021-018

Suppose that we want to build an undirected network with 200 nodes and 600 links. What will the average degree of this network be?

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

Original idea by: Hismael Costa

2021-017

What is the difference in the number of links between a compete graph \( K_7 \) and a complete bipartite graph \( K_{3,4} \)?

1. 9
   
2. 12
   
3. 15
4. 30
   
5. None of the above

Original idea by: Elian Laura

2021-016

Orion was a great warrior of ancient Greece. He was so important that Zeus created a constellation illustrating him in a fight position. Consider the graph in the image below, modeling the constellation with 15 nodes (the stars) and 16 links, without self-loops. Based on the statements below, choose the correct alternative.

(I) If Orion's belt is removed (the three nodes near the middle of the image), the resulting graph is bipartite.

(II) For any adjacency matrix for this graph, the sum of the values in the secondary diagonal is greater than or equal to the sum in the main diagonal.

(III) Removing Orion's shield (the six rightmost nodes), the resulting graph is Hamiltonian.

(IV) Removing Orion's belt and shield, the resulting graph is Eulerian.

1. Only II is correct
2. II and III are correct
3. I and IV are correct
4. All of the alternatives are correct
5. None of the above

Original idea by: André Regino

2021-015

Which of the following 4 graphs can be transformed into a bipartite graph by removing one or zero edges?
 

1)

2)

3)

4)

Choose one of the following alternatives that represents the correct answer:

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

Original idea by: Adolfo Schneider

2021-014

A general solution formula for the equation $$ 2f'(x) = f(x)^2 $$ is:

1. \( f(x) = \frac{2}{x + C} \)
2. \( f(x) = Ce^{x} \)
3. \( f(x) = - \frac{2}{x + C} \)
4. \( f(x) = \ln{x} \)
5. None of the above

Original idea by: Thales Eduardo Nazatto