Exams › GATE › Technical

Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

1. G1 = (V,E1) where E1 = {(u,v) | (u,v) ∉ E}
2. G2 = (V,E2) where E2 = {(u,v) | (v,u) ∈ E}
3. G3 = (V,E3) where E3 = {(u,v) | there is a path of length ≤ 2 from u to v in E}
4. G4 = (V4,E) where V4 is the set of vertices in G which are not isolated

Correct answer: G2 = (V,E2) where E2 = {(u,v) | (v,u) ∈ E}

Solution

G2 represents the transpose of the original graph G, where the direction of all edges is reversed. This operation preserves the strongly connected components, as the reachability between vertices remains intact in both directions.

Related GATE Technical questions

• Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?
• Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
• Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
• Which one of the following is TRUE ?
• Match the following: 1) Waterfall model 2) Evolutionary model 3) Component-based software engineering 4) Spiral development a) Specifications can be developed incrementally b) Requirements compromises are inevitable c) Explicit recognition of risk d) Inflexible partitioning of the project into stages
• Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ________ number of requests.

⚔️ Practice GATE Technical free + battle 1v1 →