Consider the graph shown in the figure below: Which of the following is a…

2008

Consider the graph shown in the figure below:

q78

Which of the following is a valid strong component?

  1. A.

    a, c, d

  2. B.

    a, b, d

  3. C.

    b, c, d

  4. D.

    a, b, c

Attempted by 65 students.

Show answer & explanation

Correct answer: D

A strong component in a directed graph is a maximal subgraph where every vertex is reachable from every other vertex within that subgraph. In the given graph, nodes A, B, and C form a directed cycle (A → B → C → A). This means you can travel from any of these three nodes to the other two, making them mutually reachable. Node D has incoming edges from A and C but no outgoing edges to return to the cycle, so it cannot be part of this component. Therefore, {A, B, C} is a valid strong component.

Explore the full course: Isro