Jawaharlal Nehru Technological University, Hyderabad M.C.A-I Semester Supplementary Examinations July 2010 DISCRETE MATHEMATICS AND GRAPH THEORY Question paper

Code No: 21001

Time: 3hours Max.Marks:60

Answer any Five questions
All questions carry equal Marks

1. a) Show that R?? S can be derived from the premises P??(Q ?? S), 7RVP and Q.
b) Explain the difference between principal disjunctive and conjunctive normal forms.

2. a) Define the term 'Lattice' clearly stating the axioms.
b) Prove that the relation "congruence modulo m" given by = = { 1 x – y is divisible by over the set of +ve integers} is an equivalence relation.

3. a) Find the total number of +ve integers that can be formed from the digits 1,2,3,4,5 if no digit is repeated in any integer.
b) How many ways are there to seat 10 boys and 10 girls around a circular table, if boys and girls seat alternatively.

4. a) Solve 5 1 6 2 2n , 2 n n n a a a nn - - - + = + = given a0 =1, a1 = 1 using generatingfunctions.
b) Solve the recurrence relation 2 1 2 5 6 3 2 1 n n n a a a n n - - + + = - + .

5. a) State criteria to detect the planarity of a connected graph and give an example also.
b) Show that two simple graphs are isomorphic if and only if their complements are isomorphic.

6. a) State and explain the Four-colour problem for planar graphs?
b) Using Grinberg theorem, find the Hamiltonian cycle in the following graph.

7. a) What is "tree traversal"? What are the different tree traversal methods? Explain them in brief with suitable examples.
b) Draw the binary tree for the following expression ((x+2) ? 3) * (4-(3+x))-5.

8. a) Describe Kruskal's algorithm to create minimum spanning tree.
b) Describe the applications of spanning trees.