1,113 views
3 votes
3 votes
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides y

Find number of strongly connected components

3 Answers

Best answer
1 votes
1 votes

A graph G is strongly connected if for all u, v there is a path from u to v and a path from v to u.

The strong components of a digraph are the maximally strong connected subgraphs


Suppose two vertices x and y , y(suppose 12) is divisivle by x(suppose 2)
x(2)-------->y(12)

But from y(12) we cannot reach x(2) as 2 is not divisible by 12.

So, all the vertices are strongly connected components.

Answer should be 11.

selected by
1 votes
1 votes

Correct.

For example, if 6 is divisible by 3, then 3 will not be divisible by 6 and so there won't be any cycle in the graph. And so each node itself will be strongly connected and so answer will be 11.

0 votes
0 votes
I think it is 0, since an edge can only be present from a lower number to a higher number, hence the lower vertices cannot be reached from higher ones. So each vertex will be a component. Any thoughts?

Related questions

0 votes
0 votes
2 answers
1
Tesla! asked Apr 30, 2017
943 views
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhat would be maximum path length bet...
1 votes
1 votes
1 answer
2
Tesla! asked Apr 30, 2017
534 views
Consider a graph where vertex having number 2 to 12 (including 2 and 12), there is an edge between two vertex x and y iff x divides yWhich vertex will have highest in deg...
1 votes
1 votes
1 answer
4
Tesla! asked Apr 21, 2018
668 views
Consider Undirected Graph Ghaving vertex V {A,B,C,D,E}and edge pair as E {AB BD BE AC CE CD}A) Given graph is disconnectedB) Given graph is completeC) Given graph has ver...