Graphs

Question

Comments

@ abhishekmehta4u

---

@ Deepakk Poonia (Dee)

---

Is 1 correct answer?

---

@ Headshot....

by adding their names in comments, they didn't know that some one asking helping to them... in GO this facility not implemented...

but you can send them private message with this question link for getting help from them

Answer 1

for G1 ... the edge present when the difference is 3

 1 ---> 4 ---> 7 ---> 10

2 ---> 5 ---> 8 ---> 11

3 ---> 6 ---> 9 ..... i mean 3 is connected to 6 and 6 is connected to 9 and so on...

Therefore no.of connected components = no.of equivalence classes = 3

 

for G2 ... the edge present when the difference is 4

 1 ---> 5 ---> 9 ---> 13 ..... i mean 1 is connected to 5 and 5 is connected to 9 and so on...

2 ---> 6 ---> 10 ---> 14

3 ---> 7 ---> 11 ----> 15 

4 ---> 8 ---> 12 ----> 16 

Therefore no.of connected components = no.of equivalence classes = 4

 

 G1 union G2 = making those two graphs as 1 but note that they are disconnected ( no new edges add between them ), means 

no.of vertices in G1 union G2 = vertices in G1 + vertices in G2 ----> (1)

no.of edges in G1 union G2 = edges in G1 + edges in G2  ----> (2)

from (1) and (2), we can conclude that

total no.of connected components in G1 union G2 = no.of connected components in G1 + no.of connected components in G2 

therefore required answer = 3 + 4 = 7

 

 

reference to union of graphs http://mathworld.wolfram.com/GraphUnion.html