adspace


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 ?

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


Please Help Members By Posting Answers For Below Questions

Draw a binary Tree for the expression : A * B - (C + D) * (P / Q)

1508


For the following COBOL code, draw the Binary tree? 01 STUDENT_REC. 02 NAME. 03 FIRST_NAME PIC X(10). 03 LAST_NAME PIC X(10). 02 YEAR_OF_STUDY. 03 FIRST_SEM PIC XX. 03 SECOND_SEM PIC XX.

1406


What sort of serious problems have you experienced, and how have you handled them?

1035


Can you declare an array without assigning the size of an array?

1225


“int a[] = new int[3]{1, 2, 3}” – This a legal way of defining the arrays?

1295


Write a program for Sorting an Array. Which sorting will you prefer?

1049