Consider an undirected graph G where self-loops are not allowed. The vertex set of G is..... : GATE-2014

Question:

Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i,
f): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a -c 1| ≤1 and
b d 1 − ≤ The number of edges in the graph is _____________.

Solution:

Satisfying conditions for |a -c 1| ≤1

 1.  condition type1 :a=c

2.   condition type2: a-c=1 or c-a=1.


 total number of pairs (a,c) satisfying condition1 : 12
 total number of pairs (a,c) satisfying condition2 : 11

so satisfying combinations for 'a' and 'c' = 11+12 =23

IN Similar way satisfying combinations for 'b' and 'd' = 23



[ a     b]
      *
[ c     d]


So total solutions = 23*23 = 529

Now there are some cases where loop exists
like :
[1,2]             [5,5]
[1,2]   OR    [5,5]

There will be 23 such cases .Why ?? :)

So remove such cases : 529-23 = 506

If you have any doubt , or have any other question , Please ask here :Waytocrack.com









No comments: