4,328 views

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$

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.

by

Can anyone explain me why D is incorrect??
Because according to me we can reach from any vertex to any vertex by simply following the directed edges of the graph, which is valid for any pair.
Please Correct me where i am wrong?
Thanks for the explanation! In the DFS tree 9 was visited after 10, but If 6 was visited after 10, we would get a totally different DFT Tree. Which is what I have done while solving. In that tree I only got 2 back edges : 2→6 and 12→11. So in general the DFT tree need not always have 3 back edges right? Which would mean option B is False?

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)

My mistake , edited.
yes i also got A,B