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
- 14261 Views
- I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
What is complexity of bubble sort?
Why do we use a multidimensional array in data structure?
What is difference between hashmap and treemap?
Why do we need to recycle?
Can you list out the areas in which data structures are applied extensively?
Why is bubble sort stable?
Why set will not allow duplicates?
What do you mean by balanced trees?
What is the difference between a Stack and a Queue.
Does treemap sort automatically?
Can we store primitives in collections?
What is difference between hashset and linkedhashset?
What is array and its types with example?
Explain what do you mean by insertion sort, bubble sort and selection sort? Also, explain the differences among the functionalities of the three sorts.
Which is faster hashmap or hashtable?
