Interested to Buy Any Domain ? << Click Here >> for more details...
Let the G be a graph with 100 vertices numbered 1 to 100
Two vertices i and j are adjecnt if | i-j| =8 or | i-j|
=12. The Number of connected components in G is ?
- 4 Answers
- 13890 Views
- I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / yogesh
as i-j=8 is connected that means
a) 1,9,17,25....are connected
b) 2,10,18.26... are connected
.
.
e) 5,13,19,27.. are connected
.
.
h) 8,16,24,32 .. are connected
|i-j| = 12 are connected
that means
t)1,13,25,27 are conncted
y)2,14,26,38 are connected
u)3,15,27,
i)4,16,28...
obv because of t, even a and e are connected.
so only four series left i.e. a,b,c,d
a and b can never be connected because of odd numbers can
never be connected to even numbers in both the series.
so only possibity left is whether a and u or b and i can
be connected .
lets see a and u
a start with 1 and increments by 8
u starts with 3 and inctements by 12
this can match somewhere only if
for any value of m and n following is true
3+12*m = 1+8*n => 1+6*m = 4*n which can never be true
hence maximum number of connecte elements is 4.
| Is This Answer Correct ? | 6 Yes | 4 No |
Answer / achintya singhal
good question
there are 4 connected components..
first contains vertices numbered 1, 5, 9,13,17,21,25,29....
second contains 2, 6, 10, 14, 18.......
third one contains 3, 7, 11, 15......
fourth contains 4, 8, 12, 16, 20.......
| Is This Answer Correct ? | 5 Yes | 6 No |
When would you use a tuple?
Mention a few applications of linked lists?
What happens if we put duplicate key in hashmap?
How to increase stack limit in w3wp.exe?
What is bitonic search?
Why is an array homogeneous?
Does concat mutate array?
How to use appendNode() in linkedlist()?
Does hashmap allow duplicate keys?
What do you mean by disjoint set adt?
Are linked lists considered linear or non-linear data structures?
What is time complexity of quick sort?
Windows 
