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 _____________. Graph Theory graph-theory discrete-mathematics graph-connectivity + – rahul sharma 5 asked Nov 14, 2017 edited Aug 7, 2021 by soujanyareddy13 rahul sharma 5 1.1k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Manu Thakur commented Nov 14, 2017 reply Follow Share I think 1 connected component will be answer 0 votes 0 votes Rohit Gupta 8 commented Nov 14, 2017 reply Follow Share How? Explain @Manu Thakur I think it will be not 1. It will depend upon choice of K. 0 votes 0 votes raviyogi commented Nov 14, 2017 reply Follow Share no bro ,there are some prime no also that make different componenets 0 votes 0 votes Manu Thakur commented Nov 14, 2017 reply Follow Share @raviyogi tell me that prime number! 0 votes 0 votes Manu Thakur commented Nov 14, 2017 reply Follow Share @rohit gupta, 2 ->4->6->-----12-->120 3->6-->-----12-----120 5--->-----20----->--- 7----->-------14------->---- all chains will connect somewhere, so graph will be connected. 0 votes 0 votes Anu007 commented Nov 14, 2017 reply Follow Share connect 61 with some vertex? 0 votes 0 votes raviyogi commented Nov 14, 2017 reply Follow Share plz check my answer @Manu thakur 0 votes 0 votes Shivam Chauhan commented Nov 14, 2017 reply Follow Share @Manu What type of connected components are being referred here? Because for directed graph we have strongly connected components and weakly connected components. There is an edge from a to b if b = K * a where k is any natural number Take k = 1 2-->3-->4...........-->120 3-->4...........-->120 4...........-->120 .................. 119-->120 Weakly connected components = 1 Strongly connected components = 119 0 votes 0 votes Manu Thakur commented Nov 14, 2017 reply Follow Share @raviyogi your answer seems correct! 1 votes 1 votes Anu007 commented Nov 14, 2017 reply Follow Share can 2 and 3 will be conncted.? shivam 0 votes 0 votes Shivam Chauhan commented Nov 15, 2017 reply Follow Share I got it @Anu007 @raviyogi answer is correct 0 votes 0 votes Please log in or register to add a comment.
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 raviyogi answered Nov 14, 2017 selected Nov 14, 2017 by Manu Thakur raviyogi comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Kiran Karwa commented Jan 12, 2018 reply Follow Share How to find all prime numbers between a set of numbers without missing out any? 0 votes 0 votes raviyogi commented Jan 12, 2018 reply Follow Share if you are stuck finding prime numbers just follow this trick-> to find if n is prime or not folow the procedure 1.find (square root of n) 2.now try to divide n only by the numbers <= (square root of n). 3.if it is not divisible by any then it is prime. IT will save your time 1 votes 1 votes adactive18 commented Jan 25, 2018 reply Follow Share @ rohan mishra Because prime numbers below 60(i.e. p)are connected with 2p, which is even and less than 120. So, that 2p will get connected to rest of all via 2. 0 votes 0 votes Please log in or register to add a comment.
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. rish1602 answered Jun 8, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.