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
- 14107 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 |
What is linear-logarithm chasm?
What are the properties of an algorithm?
No. of possible ordered trees with n nodes ? Please give formula (if any).
State the difference between stacks and linked lists?
Is binary tree a bst?
Why we need cursor implementation of linked lists?
Can hashtable have duplicate values?
Is pointer a variable in data structure?
Can treemap have null values?
What are the best data structure courses for gate preparation?
How does a hashtable work?
What differences exist between hashmap and hashtable?
Windows 
