Question 6 - Degree Correlations

Consider a directed graph D. Which of the following statements about Strongly Connected Components (SCC) are correct?

A. In D, an SCC is a subgraph where for every pair of nodes u and v, there is a directed path from u to v and from v to u.

B. Given two distinct SCCs in D, there can be at most one edge connecting them in any direction.

C. The condensed graph of D, formed by its SCCs, is a Directed Acyclic Graph (DAG).

Options:

a) A

b) A and C

c) B and C

d) A, B and C

e) None of the above

Original idea by: Sergio Sanchez

Comentarios

Publicar un comentario

Entradas populares de este blog

Question 1 - DFS

During a Depth-First Search (DFS) on a directed graph G, the following edges are observed: The edge (u, v) connects node u to node v, which has already been visited and fully explored. The edge (x, y) connects node x to node y, which has been visited but not fully explored yet. The edge (a, b) connects node a to node b, which has been fully explored, but b belongs to a different branch in the DFS tree. Which of the following options correctly classifies these edges according to their type in a DFS traversal? A) (u, v) is a forward edge, (x, y) is a back edge, (a, b) is a back edge. B) (u, v) is a cross edge, (x, y) is a forward edge, (a, b) is a tree edge. C) (u, v) is a forward or cross edge, (x, y) is a back edge, (a, b) is a cross edge. D) (u, v) is a back edge, (x, y) is a cross edge, (a, b) is a forward edge. E) (u, v) is a cross edge, (x, y) is a back edge, (a, b) is a tree edge. Original Idea by Sergio Sanchez
Leer más

Question 2 - Graph Theory

Let G be a simple, undirected, and connected graph with n vertices. Consider the following statements: A. If (u, v) is a bridge in G, then at least one of the vertices u or v is a cut vertex. B. The maximum number of bridges that G can have is n-1. C. If G is a tree with more than 2 vertices and with f leaves, then the minimum number of edges that need to be added so that there are no bridges is ⌈f/2⌉. Select the alternative that identifies the incorrect statements: a) A and B b) B and C c) Only A d) Only C e) None of the above Original Idea by Sergio Sanchez
Leer más

Question 3 - BFS

Consider the following statements: A. Given a tree T, it is possible to find the diameter of T using two BFS executions. B. If an undirected graph is bipartite, it can be detected using BFS. C. BFS was run on a connected simple graph, starting from a node r. Let u and v be two nodes in the graph. If the distance from r to u is 2, and the distance from r to v is 1, then the distance between u and v in the graph must necessarily be 1. Which of the statements are correct? a) Only A b) Only B c) A and B d) B and C e) None of the above
Leer más