BPUT MCA Discrete Mathematics question paper 2013

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 C_n=3C_n-1-2C_n-2 with initial conditions C₁=5, C₂=3.5

3. (a) If R is a relation defined on A={a1,a2,a3.....an}, then show that
M_R²=M_R * M_R5

(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:
M_R= 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:x²=e}. Show that H is a subgroup of G.5

7.(a) Let n=p₁p₂p₃...p_k, where the p_k are distinct primes. Then show that D_n, 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