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 requirement relationship is defined by a direct link, in which a course describes its prerequisites to be enrolled.

For example:

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

Note: courses are nodes, prerequisite requirements are links, and the image is a network.

On the figure, consider the following sentences and mark them 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 that matches 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 E have the same clustering coefficient.

B) 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.

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

D) The node C has the highest clustering coefficient.

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

2023-195

 Consider the ten-node graph and the degree distribution plot in the following figures:

Fig. A

Fig. B

The degree distribution plot shown in Fig. B was generated after removing a single link from the graph in Fig. A. Which of the following alternatives correctly identifies potential link(s) that could have been removed to produce that degree distribution?

1. BC or FH
2. BD or DF or FG
3. BE or DF or FG
4. IJ
5. none of above

Original idea by: Anderson Nogueira Cotrim

2023-194

Consider the bipartite network in which the nodes are animals and the nodes are environments. If an animal \( a \) lives in an environment \( e \), then there is a link between \( a \) and \( e \). Take the following image as an example of part of this network.

If a scientist wants to know possible interactions among animals, they need to know which ones live together. One way to determine this it to:

1. Get all nodes of \( A \); only the ones with the same degree live in the same environment
2. Calculate the probabilistic distribution \( p_k \) of degrees; if \( p_k \) is the same for two values \( k_1 \) and \( k_2 \), then the nodes of \( A \) with degree \( k_1 \) live together with the ones of degree \( k_2 \)
3. Calculate the projection on \( A \); if two animal nodes are connected in the projection, then they share the same environment
4. Check which nodes of \( A \) are connected; if they are, they share the same environment
5. None of the above

Originasl idea by: Christian Konishi

2023-193

Given the graph in the figure below, evaluate the assertions:

graph Rede {

A -- B [label="10 Gbps"]

A -- C [label="10 Gbps"]

B -- D [label="10 Gbps"]

B -- E [label="100 Mbps"]

E -- C [label="100 Mbps"]

H -- F [label="10 Mbps"]

E -- F [label="100 Mbps"]

F -- G [label="100 Mbps"]

C -- F [label="10 Mbps"]

B -- G [label="10 Mbps"]

D -- H [label="1 Gbps"]

A -- E [label="100 Mbps"]

E -- H [label="1 Gbps"]

}

view raw Rede.gv hosted with ❤ by GitHub

1. There are two paths from router 'A' to router 'H' that are identical in maximum speeds and same path lenght.
2. The average degree of this graph is 3.25.
3. 32.5% of the nodes have a degree of 3.
4. The fastest path between router 'A' and router 'G' has a bandwidth capacity of 100 Mbps.
5. The graph's adjacency matrix is not symmetric.

Choose the alternative listing the true statements:

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

Original idea by: João Marcos

2023-192

The famous Königsberg bridge problem, considered by many as the origin of graph theory, asks if all city bridges can be crossed without repetition in a single trip. 

Euler proved that it was impossible to do that. One of the reasons for that was:

1. The nodes have different degrees.
2. One or more nodes with an odd degree make a single trip impossible.
3. The four nodes (pieces of land) had an odd degre (number of bridges).
4. A single trip is only possible when the number of lands are equal to the number of bridges.
5. None of the above.

Original idea by: Lucas Carvalho Roncoroni.