2023-206

 

Imagine a Cayley Tree, constructed starting from a central node, where each node has degree \(k\), except the nodes at distance P from the central node, that have degree one, as shown in the figure above. Considering that the number of nodes reachable in \( t \geq 1 \) steps from the central node is \( k(k-1)^{t-1} \), and the number of links is \( L = N-1 \), where \( N \) is the number of nodes, what is the probability of conexion between nodes for \(k=4\) and \(P=4\)?

1. 1/161
2. 2/161
3. 1/41
4. 2/41
5. None of above

Original idea by: Germán Darío Buitrago Salazar

2023-205

Suppose that we are trying to project a distributed system with random architecture. Every time a new computer \( i \) tries to ingress, for each existing machine \( j \) in the network, a connection \( (i,j) \) may be created with probability \( p \).

For this architecture, it is desired that any computer must be reachable from any node, however a few exceptions are tolerable. Also, \( p \) cannot be too big for cost reasons.

Which one of these options presents a reasonable choice for the value of \( p \)? Assume that\( N \) is the number of expected computers in the network, and it is large enough to apply the law of large numbers.

1. \( p = \frac{1}{N} \), because it is the critical point.
2. \( p = \frac{\ln N}{N} \), because it is the boundary between the supercritical and the connected regime.
3. \( p = \frac{\ln N}{\ln \langle k \rangle} \), because it is the boundary between the supercritical and the connected regime.
4. \( p = \frac{\langle k \rangle}{N} \), because it is the critical point.
5. None of the above

Original idea by: Christian Konishi

2023-204

Considering the Gilbert model , which statements from the following list are correct?

1. The expected number of links in a network generated with this model is \( \frac{pN(N-1)}{2} \)
2. If \( p > \frac{\ln N}{N} \) this model always generates a fully connected network with 100% certainty
3. This model produces a degree distribution that follows a Poisson distribution, which can be approximated by binomial distribution when \( N \) is much larger than \( k \)
4. A complete network can be generated from this model when \( p > 0 \), even if this is not likely

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

Original idea by: Anderson Nogueira Cotrim

2023-203

Given the following adjacency matrix that represents a directed graph (a '1' in row \(x\) and column \(y\) means a directed link \(x \rightarrow y\)), apply a topological sort using Depth First Search (DFS) and determine the start and finish times for each node. Start from node 'a' and always prioritize visiting nodes in alphabetical order.

	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)	\(g\)
\(a\)	0	1	0	0	0	0	0
\(b\)	0	0	1	0	1	0	0
\(c\)	0	0	0	1	0	0	0
\(d\)	0	0	0	0	1	0	1
\(e\)	0	0	0	0	0	1	0
\(f\)	0	0	0	0	0	0	0
\(g\)	0	0	0	0	0	1	0

1. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(6,7); g(5,8)
2. a(1,14); b(2,13); c(3,12); d(4,11); e(5,7); f(6,9); g(8,10)
3. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(7,8); g(6,9)
4. a(1,14); b(2,13); c(3,12); d(4,11); e(5,8); f(6,7); g(9,10)
5. None of the above

Original idea by: Thaysa Bello

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