Total number of printed pages — 2
MCA
MCC 103
First Semester Examination — 2012-13
DISCRETE MATHEMATICS
Full Marks • -70
Time: 3 Hours
Answer Question No.1 which is compulsory and any five from the rest.
The Figure in the right hand margin indicate marks.
Q1. Answer the following questions: 2*10
(i)Let A = {a, b, c, d}. The relation R = { (a, a), (a, b),(b, c) } is defined on A. Find R2.
(ii)) If {1{3, 5} , {2, 4}} is a partition of the set A = {1, 2, 3, 4, 5}, determine the corresponding equivalence relation R.
(iii) What do you mean by symmetric closure of a relation ?How can you find the symmetric closure of a relation R defined on the set A ?
(iv) Can you find a cycle of length greater then one in a diagraph representing a partial order relation? Justify your answer?
(v) For any two elements a, b of a lattice, show that a v b=b iff a <= b ?
(vi) Is there any Boolean algebra having nine elements ?Justify your answer?
(vii)State i arrange theorem of a finite group? Give example of a finite group having a non-trival subgroup.
(viii)What is a Hamiltonian graph ? Give example of a Hamiltonian graph.
(ix) What is an Euler path ? What is the necessary condition for a graph to possess an Euler path ?
(x)What is a group code ? Howcan you had the minimum distance of a group code ?
2.(a)Prove by mathematics induction that the product of three consecutive positive integers are divisible by 3. 5
(b) Find an explicit formula for the sequence defined by Cn=3Cn-1-2Cn-2 with initial conditions C1=5, C2=3.5
3. (a) If R is a relation defined on A={a1,a2,a3.....an}, then show that
MR2=MR * MR5
(b) State warshall algorithm to find the transitive closure of a relation. Hence find the transitive closure of a relation R defined on the set {a,b,c,d} whose matrix representation is given below:
MR= 5
4.(a) Let L be a bounded lattice with atleast two elements. Show that no elements of L is its own complement.5
(b) Let L be a distributive lattice. Show that if there exist an element a with
a x=a y and a v x = a v y then x=y5
5(a) Define a tree. Write the algorithms of postorder, inorder and preorder traversal of a tree.4
(b) Write the kruskal's algorithm to find a minimal spanning tree for a graph. List the edges in the order in which they are chosen
6
6.(a) Let N be a normal subgroup of a group G and let R be the following relation on G
a R b if and only if a-1b is in N.
Then show that R is a congruence relation in G.5
(b) Let G be a abelian group with identity element e and H={x:x2=e}. Show that H is a subgroup of G.5
7.(a) Let n=p1p2p3...pk, where the pk are distinct primes. Then show that Dn, the set of all positive integer divisors of n, is a boolean algebra.5
(b) Show that in a boolean algebra, for any a and b,
b (a v(a' (b v b')))=b5
8. Explain the followings:2.5*4
(a) Hasse diagram of a Poset.
(b) Quotient group
(c) Breadth First Search
(d) Chromatic number
Subscribe with us to get latest topic update