retagged by
8,608 views
15 votes
15 votes

Consider the following directed graph:

Which of the following is/are correct about the graph?

  1. The graph does not have a topological order
  2. A depth-first traversal starting at vertex $S$ classifies three directed edges as back edges
  3. The graph does not have a strongly connected component
  4. For each pair of vertices $u$ and $v$, there is a directed path from $u$ to $v$
retagged by

3 Answers

Best answer
17 votes
17 votes

Lets put numberings to the nodes as follows:

The back edges are those edges from $v$ to $u$ in set $(u,v)$ where $u$ came first (i.e. already explored) in the DFS tree/forest.

  • $3$ to $2$
  • $12$ to $11$
  • $9$ to $S$

The DFS tree:

The graph has two cycles one at bottom left and one at bottom right. And every cycle forms SCC (Strongly connected component, since from every vertex $u,$ there is a path to $v, \bf{u \to v})$. C is false

The entire graph doesn’t have SCC. So, definitely D is false. 

Due to the presence of cycles Topological Sort is not possible.

Hence, the answer is A and B.

D would have been correct if it was For some pair of vertices u and v there is a directed path from u to v.

selected by
5 votes
5 votes

A) The graph does not have a topological order , because there’s a cycle in the bottom left corner of the graph

B) Yes, there are only 3 back edges, if started from S.

C) The graph does have a strongly connected component , it has cycle .

D) False , you can observe and find that not all rectangular/square components forms a cycle.

So answer : A) , B)

edited by
0 votes
0 votes

Note: Topological Sorting for a graph is not possible if the graph is not a DAG.

Hence Option(A) is correct

Option(B) is correct .There are 3 back edges from Vertex S  (Back edge: It is an edge (u, v) such that v is the ancestor of node u but is not part of the DFS tree).

Option(D) is incorrect as for each pair of vertices there is not a directed path available

Option(C) is incorrect because Strongly connected component is present in the graph

example of strongly connected graph is 

scc_fianldrawio

 

Answer:

Related questions