12-06-2014, 04:30 PM
IV SEMESTER II MID TERM EXAMINATION- 2011-12 ==B.TECH II YEAR (CSE & IT)
1370368069-DMSPPPP.doc (Size: 124 KB / Downloads: 15)
SUBJECT: DISCRETE MATHEMATICAL STRUCTURES
1. Attempt all the questions.
2. The number printed against the question shows the marks allotted to the question or its parts.
3. Assume any missing data suitably and justify it.
1. Let R be an equivalence relation on a non empty set A. then 5
(i) aЄ [a] for each a ЄA,
(ii) [a]= [b] if and only if (a ,b ) Є R ,
(iii) Either [a] Λ [b] =ф or [a] =[b]; a, b Є A
OR
45 candidates appear in a competitive examination. Prove that there are at least two candidates whose roll numbers difference by a multiple of 44. 5
2. find the minimal spanning tree for a given weighted connected graph apply a kruskal s algorithm. 5
OR
(a) Let A =( a, b ,c ,d) B = (c,e,f,h,k,m) then prove if A and B are finite sets then 2.5
A U B = A + B - AΛB
(b) Let A = ( 1,2,3,4) and consider the partition P = { (1,2,3) , (4) } of A . obtain the equivalence relation R on A determined by P. 2.5
3. Show that n< for all positive integers. 5
OR
Using warshall algorithms to obtain the transitive closure of a relation R. shown in the following figure : 5
4. A connected graph G is Euler graph if and only if it has no vertex of odd degree. 5
OR
State and prove Euler’s formula 5