Amrita Vishwa Vidyapeetham 2007 M.C.A Discrete Mathematics - Question Paper

M.C.A. MAY 2007

Discrete Mathematics

Time : 3 hours Maximum : 100 marks
ans any 5 of the subsequent.
(5 ? 20 = 100)
1. (a) Define well formed formulae and construct truth table for . (10)
(b) Explain principal disjunctive normal form. (10)
2. (a) Define Poset. Let and the relation be such that if x divides y. Draw the Hasse diagram of . (10)
(b) Let and is divisible by 3}. Show that R is an equivalence relation on X. and also draw the graph of R. (10)
3. (a) Define coset of a group. Prove that the order of a subgroup of a finite group divides the order of the group. (10)
(b) Let g be a homomorphism from a group to a group and let k be the Kernel of g and be the image of g in H. Then is isomorphic to . (10)
4. (a) Define Monoid homomorphism. Let be a provided semigroup. Prove that there exists a homomorphism
where is a semigroup of functions from
S to S under the operation of composition. (10)
(b) Define an abelian group. Prove that the set of rational numbers excluding zero is an abelian group. (10)
5. (a) Let A be the set of factors of a particular positive integer m and let be the relation divides
i.e.
Draw Hasse diagrams for the subsequent
(i) (ii) (iii) (iv)
(v) and (vi) . (10)
(b) Define compatibility relations. Let the compatibility relation on a set be provided by the matrix.

1

1 1

0 0 1

0 0 1 1

1 0 1 0 1






Draw the graph and obtain the maximal compatibility blocks of the relation.
6. (a) Write notes for the subsequent : (10)
(i) Subgraphs
(ii) Paths
(iii) Circuits
(iv) 2Terminal vertices.
(b) Define unicursal graph. In a connected graph G with exactly 2k odd vertices there exist k edge disjoint subgraphs such that they together contain all edges of G and that every is a unicursal graph. (10)
7. (a) Draw all possible trees of 6 vertices prove that a tree with n vertices has edges. (10)
(b) Prove that every tree has either 1 or 2 centres.
8. (a) Define Adjacency Matrix and write the observations of Adjacency Matrix. (10)
(b) Define circuit matrix with example write the matrix for the subsequent graph

Earning:   Approval pending.