edited by
1,084 views
9 votes
9 votes
Consider $G$ be a directed graph whose vertex set is a set numbers from $2$ to $120$. There is an edge from vertex $b$ if $b=K\times a$. Where $K$ is any natural number. Then the number of connected components are _____________.
edited by

2 Answers

Best answer
7 votes
7 votes
if we see every prime number in range (60-120) did not satisfy  b=k*a for any number hence they make different components .

these prime numbers are {61,67,71,73,79,83,89,97,101,103,107,109,113).

hence no of components =13+1=14
selected by
0 votes
0 votes

Since all the numbers can be expressed as  (p1^a)(p2^b)(p3^c)………

where p1, p2, p3, p4…. are the prime numbers and a, b, c, d...are its powers. Thus total divisors are (a+1)(b+1)(c+1)...

Hence it becomes clear that numbers which can be expressed in the above mentioned form along with its divisors, will for a component. And rest other prime numbers between [ 61, 120] i.e. 13 such prime numbers + 1 of the above pattern= total 14  will be components in the graph.

Related questions

3 votes
3 votes
3 answers
1
rahul sharma 5 asked Jun 12, 2017
1,911 views
What are the chromatic number of following graphs?Answer is 6 and 4 respectively.But i am getting 3 for both.Please someone confirm this?
3 votes
3 votes
1 answer
2
rahul sharma 5 asked Jun 7, 2017
1,254 views
What is the vertex connectivity and edge connectivity of complete graph?Is it n or n-1?
2 votes
2 votes
2 answers
3
rahul sharma 5 asked Jun 12, 2017
1,982 views
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
2 votes
2 votes
0 answers
4
Manu Thakur asked Dec 3, 2017
1,165 views
Let G be a 3-regular graph and S be a minimum vertex cut of G with |S| = 5The the size of smallest edge cut of G is _______(A)4(B) 5(C) 6(D) None of the above