Consider the following directed graph:

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

This question was previously asked in

GATE CS 2021 Official Paper: Shift 2

Option :

IBPS SO IT Officer Mains: Full Mock Test

5486

60 Questions
60 Marks
45 Mins

** Answer**: Option 3 and Option 4

__ Concept__:

**Strongly Connected Graph**:

The directed graph in which every vertex can be reached from any other vertex.

**Strongly Connected Component**:

**A** **strongly connected component** of a directed **graph** is a maximal **strongly connected** subgraph.

**Topological Order**:

Graph must not contain any cycle for topological ordering to exist in a graph.

__ Explanation__:

__ Option 1__:The graph does not have a strongly connected component.

This statement is **false **as There exists ASBC, this rectangle is a strongly connected component as __ we can reach all the vertices in the component__ from any vertex in the component.

__ Option 2__: For each pair of vertices u and v, there is a directed path from u to v.

This statement is also __ false __as from

__ Option 3__: The graph does not have a topological order.

__As you can observe there exists cycles in the graph so topological ordering not possible.__

This Statement is __ correct__.

** Option 4**: A depth-first traversal starting at vertex S classifies three directed edges as back edges.

This Statement is __ correct__.

In DFS tree back edges indicates __ cycle in the graph__.