PGEE 2017

Question

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

Comments

there is an edge between two vertex x and y iff x divides y

there is an edge between 2 and 12 iff 2 divides 12. 

how are we assuming that it is a digraph? also how are we assuming that there is an edge from 2 to 12 and not 12 to 2?

---

@ Mk Utkarsh in the undirected graph, there is no concept of SCC so it's logical to assume graph is directed, otherwise

there is an edge between two vertex x and y iff x divides y

don't make any logic. and it changes relation from x divide y to "x is factor of y and y is multiple of x

---

ok but still i find question a bit ambiguous.

Answer 1

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.

Answer 2

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.

Comments

@ edited check the new answer.

Answer 3

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?

Comments

The answer should be 11.

Take any two vertices v1 and v2,

if v1 can reach v2, v2 can not reach v1.

So, all the vertices are strongly connected components.

---

Yeah, agree with you. It should be 11