Biju Patnaik University of Technology 2008-1st Sem M.C.A Discrete Mathematics - Question Paper

Ffrst Semester Examination - 2008 DISCRETE MATHEMATICS Full Marks-70 Time 3 Hours

Answer Question No. 1 which is compulsory and any five from the re si

IWL The figures in the right hand margin indicate

futf marks tor the questions,

1. Answer the following questions : 2x10

'(I) Is the following statement a tautology ? t

Justify your answer, p (q p)

(ii) Let A = {a, b_f c, d>. Tine relation R = <{a₍ a), {a, b), (b, c), (c, d)) is defined i    on A. Find R².

RT.O.

(Iii) If {{1, 3. 5), {2. 4}) is a partition of the

y'

t set A = f1 2. 3, 4, 5, determine the corresponding equivalence relation R.

{iv) 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 ?

(v)    Can you find a cycle of length greater than one in a diagraph representing a partial order relation ? Justify your answer

(vi)    For any two elements a,b of a lattice .show that avb = bifa< b.

(vii)    Is there any Boolean algebra having nine elements ? Justify your answer.

(viii)    Write the algorithm of preorder and post

jf order searching of a tree.

(ix)    How can you know whether an undirected graph possesses an lEuler path or not ?

(x) What do you mean by minimum distance of an encoding function ? How can you find the minimum distance of a group code ?

{a) Prove by mathematical Induction that n divides n³ - n for every positive integer n.

5

Find an explicit formula for the sequence

<b)

defined by C - 3C - 2C * with initial

^J r    n1    ft*

conditions C ,= 5 and C. = 3,

¹ 1 2

(a)    If R is a relation defined on A = {a _t, a₂, a.j_t ... a_n}₍ then show that M_r1 ~ M_r M*. 5

(b)    State Warshall Algorithm to find the transi-

j

live closure of ablation¹. ^fHence, find the transitive closure of a relation R defined on the set {a, b, c_p d} whose matrix represen

tation is given below.

0 0 0 1 0 0

0 1 0

0 0 1

A_t (a) Let L be a bounded lattice with at least two elements. Show thal no element of L is its own complement.    5

(b) Lei A be a finite nonempty poset with partial order < . Show that A has at least one maximal element and at least one minimal element.    5

5,. (a) Let the number of edges of a graph G be m and number of vertices be n. Then show that G has a Hamiltonian circuit if m > Yi {n² - 3n + 6),    5

(b) Find a maximum flow in the given network where each edge is labelled with its maximum capacity ; node 1 being the source and node 8 being the sink, 5

(a) Write the KruskaPs algorithm to find a minimal spanning tree lor a graph. Using the algorithm, find a minimal spanning tree for the following graph. List the edges in the order in which they are chosen. 5

IWL

(b)' Let R be a symmetric relation on a set A. Theoprove that the following statements are equivalent    5

(i) R is an undirected tree

(iii) R is connected and acyclic,

(a) Show that the intersection of two congruence relation on a semigroup is a congruence relation.    5

Jp) "Let G be an abefian group with identity element e and W = 4 x x^? = e). Show that H is a sub group of G.    5

B, (a) Let n = p_fpjp_3tt.p_t( where the p, are distinct primes* Then show that D_[(V the set o! all positive integer divisors of n_f Is a boolean algebra.    5

(b) Show that in a Boolean algebra, for aiiiy a and b,

(a v b) v (a a b*T= a    5

IWL

Attachment: biju-patnaik-university-of-technology-2008-m-c-a--36306-1.pdf

Earning:   Approval pending.