###### Question 1617 – ISRO CS 2015

May 22, 2024###### Question 176 – ISRO CS 2008

May 22, 2024# Question 8451 – Engineering-Mathematics

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?

Correct Answer: B

Question 92 Explanation:

G(V, E) is a directed graph.

→ It strongly connected.

(A) G

If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.

(B) G

Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.

Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.

(C) G

This can also be true.

eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.

(D) G

If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component

then no. of SCC = x + 1

G

→ It strongly connected.

(A) G

_{1}=(V,E_{1}) where E_{1}={(u,v)|(u,v)∉E}If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.

(B) G

_{2}=(V,E_{2})where E_{2}={(u,v)│(u,v)∈E}Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.

Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.

(C) G

_{3}=(V,E_{3}) where E_{3}={(u,v)|there is a path of length≤2 from u to v in E}This can also be true.

eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.

(D) G

_{4}=(V_{4},E) where V_{4}is the set of vertices in G which are not isolated.If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component

then no. of SCC = x + 1

G

_{4}contain only ‘1’ component, which is not same as G.G

_{1}=(V,E_{1}) where E_{1}={(u,v)|(u,v)∉E}G

_{2}=(V,E_{2})where E_{2}={(u,v)│(u,v)∈E}G

_{3}=(V,E_{3}) where E_{3}={(u,v)|there is a path of length≤2 from u to v in E}G

_{4}=(V_{4},E) where V_{4}is the set of vertices in G which are not isolated
Subscribe

Login

0 Comments