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
- 14108 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 |
Write a Program for Linked list manipulation.
How do you find a string is anagram or not?
Can tuple be sorted?
State the merit of linked representation of binary trees?
Difference between arraylist and linkedlist?
What is the main advantage of a linked list?
Can we store null in arraylist?
What is data structure and its operations?
Explain the expression trees?
How do you implement a stack?
Define primary clustering?
Which is faster hashmap or linkedhashmap?
Windows 
