GATE CS 2014 Set 1 — Question 13

To find which graph has the same strongly connected components (SCCs) as $G = (V, E)$, let us analyze the definition of a strongly connected component and the properties of the given options.

1. Definition of Strongly Connected Components (SCCs)

In a directed graph $G = (V, E)$, two vertices $u$ and $v$ belong to the same strongly connected component if and only if there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$ in $G$. We denote this mutual reachability relation as $u \leftrightarrow v$.

2. Analysis of Option B: The Transpose Graph $G_2$

The graph $G_2 = (V, E_2)$ is defined by reversing the direction of all edges in $G$:$$E_2 = \{(u,v) \mid (v,u) \in E\}$$This graph $G_2$ is known as the transpose graph of $G$, often denoted as $G^T$.Let us determine the reachability relation in $G_2$:

• A directed path from $u$ to $v$ exists in $G$ if and only if there is a directed path from $v$ to $u$ in $G_2$.
• Similarly, a directed path from $v$ to $u$ exists in $G$ if and only if there is a directed path from $u$ to $v$ in $G_2$.

Therefore, two vertices $u$ and $v$ are mutually reachable in $G$ if and only if they are mutually reachable in $G_2$:$$u \leftrightarrow v \text{ in } G \iff u \leftrightarrow v \text{ in } G_2$$Since the equivalence relation of mutual reachability is identical for both $G$ and $G_2$, the equivalence classes (which are the strongly connected components) are exactly the same for both graphs.---

3. Why Other Options are Incorrect

• Option A ($G_1$): $G_1$ is the complement graph. Changing the edge set to non-existent edges completely alters the reachability structure. For example, if $G$ is a single directed cycle of 3 vertices (which is strongly connected), its complement $G_1$ will not be strongly connected.
• Option C ($G_3$): $G_3$ adds transitive shortcut edges of length $\le 2$. This can merge separate SCCs of $G$ into a single SCC. For example, if $G$ is a path $a \to b \to c$, the SCCs of $G$ are $\{a\}$, $\{b\}$, and $\{c\}$. In $G_3$, we add the edge $(a, c)$, but there is still no path back, so the SCCs remain the same in this specific case, but if we have $a \to b \to c$ and $c \to a$, adding paths of length $\le 2$ can create new cycles and merge components that were not originally connected in both directions. More simply, $G_3$ changes the reachability relation and does not preserve the exact SCC boundaries in all graphs.
• Option D ($G_4$): $G_4$ modifies the vertex set by removing isolated vertices ($V_4 \subseteq V$). If $G$ contains any isolated vertices, they form their own single-vertex SCCs. Removing them means $G_4$ will have fewer SCCs than $G$.

Thus, only the transpose graph $G_2$ is guaranteed to have the exact same strongly connected components as $G$.Correct Answer: Option B