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
- 14248 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
Mention the data structures which are used in graph implementation.
What are the properties of binary tree?
What is declaring array?
List out the applications of a linked list?
What do you mean by tree edge?
What is integer max_value?
What do you mean by rehashing?
What is sequential search?
How can you represent a linked list node?
Can we override compareto method for enumerations?
What is the purpose of thread?
What is the difference between linked list and array?
What is hashing technique? Describe in brief.
How do you replace an element in an arraylist?
Which sorting algorithm has minimum number of swaps?
