C onsider a directed graph G and the concept of Strongly Connected Components (SCC). Analyze the following statements, and choose the right answer: I- In a directed tree, each vertex is considered a SCC. II- Every cycle in a directed graph G always constitutes its own separate SCC. III- A trivial graph G cannot be considered as a SCC. a) I and II are correct. b) II and III are correct. c) Only I is correct. d) Only III is correct. e) None of the above. Original idea by: Tássia Martins
Posts
Look at the adjacency matrix of a directed graph below, analyze the statements, and choose the right answer: $$ A_{ij} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{pmatrix} $$ OBS: To BFS and DFS consider starting at node 1 and in an ascending order. I - This graph has a Cycle, so we can say that there is at least one back edge. II - The order that the nodes are visited using DFS is 1-4-2-6-7-5-3. III - The order that the nodes are visited using BFS is 1-4-5-2-6-7-3. IV - Besides the graph presented by the matrix being a directed graph, in an undirected graph there are no forward and no cross edges. a) I, II, III and IV are co...
Look at the figures below and choose the right answer: I- The graph in figure A is a Multigraph and in figure B is a simple graph. II- In a complete graph, known as clique, all nodes are connected to each other. III- The diameter of the graph in figure B is d max = 4. IV- The adjacency matrix of graph in figure B is: a) I and II are correct b) II, III and IV are correct c) II and IV are correct d) I, II, IV are correct e) None of the above