DISCRETE STRUCTURES AND GRAPH THEORY

JAN 2010-MCA I SEM QUESTION PAPER(JNTUK)

Time: 3 Hours Max Marks: 60

Answer any FIVE questions All questions carry EQUAL marks



1. a) Find the conjunctive normal form and disjunctive normal forms for

i) p (p¢Úq¢)

ii) (pÚq¢)® q

b) Determine the contra positive of the each statement

i) If john is a poet, then he is poor.

ii) Only if Marc studies well he pass the test



2. a) Express the following statements using quantifiers. Then construct the

negation of the statement

i) Every bird can fly

ii) Some birds can talk

b) Prove that if n is an integer and n3+5 is odd then n is even.



3. Let R be a binary relation on the set of all positive integers such that

R = { (a,b)/ a-b is an add positive integer}

Is R Reflexive? Symmetric? Antisymmtric? Transitive? An equivalence

relation? A partial ordering relation?



4. a) let (A, *) be a semi group. Show that, for a, b, c in A, if a*c=c*a and

b*c=c*b, then (a*b)*c = c* (a*b)

b) Let f and g be homomorphism from a group (G, +) to a group (H,*). Show

that (C,+) is a subgroup of (G,+), where C={ xÎ G\ f(x)=g(x)}



5. a) Find the sum of all four digit numbers that can be obtained by using (without

repetition) the digits 2, 3,5 and 7.

b) Enumerate the number of ways of placing 20 indistinguishable balls in to 5 boxes

where each box is non empty.



6. a) Solve the recurrence relation tn = 4(tn-1 – tn-2 ) subject to initial condition

tn=1 for n=0 and n=1

b) What is an nth order linear homogenous recurrence relation with constant

coefficients? Give examples



7. a) What are the necessary and sufficient conditions to specify that two

graphs are isomorphic. Explain with an example.

b) Briefly explain Prim’s algorithm for minimum spanning trees.



8. Give example for each of the following

i)Graph having Euler’s circuit

ii)Graph having Hamiltonian circuit