Jawaharlal Nehru Technological University Hyderabad 2010-1st Sem M.C.A -ester Supplementary s DISCRETE MATHEMATICS AND GRAPH THEORY - Question Paper
Tuesday, 02 July 2013 09:10Web
Code No: 21001
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
MCA-I Semester Supplementary exams July 2010
DiscRETE MATHEMATICS AND GRAPH THEORY
Time: 3hours Max.Marks:60
ans any 5 ques.
All ques. carry equal Marks
- - -
1. a) Show that R?? S can be derived from the premises P??(Q ?? S), 7RVP and Q.
b) discuss the difference ranging from principal disjunctive and conjunctive normal
forms.
2. a) describe the term 'Lattice' clearly stating the axioms.
b) Prove that the relation "congruence modulo m" provided by = = {
divisible by over the set of +ve integers} is an equivalence relation.
3. a) obtain 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 five one six two 2n , 2
n n n a a a nn - - - + = + = provided a0 =1, a1 = one using generating
functions.
b) Solve the recurrence relation 2
1 two five six three two one n n n a a a n n - - + + = - + .
5. a) State criteria to detect the planarity of a connected graph and provide an example
also.
b) Show that 2 simple graphs are isomorphic if and only if their complements are
isomorphic.
6. a) State and discuss the Four-colour issue for planar graphs?
b) Using Grinberg theorem, obtain the Hamiltonian cycle in the subsequent graph.
7. a) What is "tree traversal"? elaborate the various tree traversal methods? discuss
them in brief with suitable examples.
b) Draw the binary tree for the subsequent expression ((x+2) ? 3) * (4-(3+x))-5.
8. a) define Kruskal's algorithm to create minimum spanning tree.
b) define the applications of spanning trees.
*****
NR
| Earning: Approval pending. |
