Pachavellam UG-PG

D73252

D 73252

 FIRST SEMESTER B.A./B.Sc. DEGREE EXAMINATION

 NOVEMBER 2019

 (CBCSS-UG)

 BCA

 BCA 1C 02-DISCRETE MATHEMATICS

 (2019 Admissions)

 Time : Two Hours          Maximum:60 Marks

Section A (Short Answer Type Questions)

 Answer all questions, each correct answer carries

a maximum of 2 marks. Ceiling 20 marks.

 1. Symbolize the statement All men are giants".

 2. Draw the truth table of biconditional statement .

 3. Give an example of a relation which is both symmetric and antsrymmetric.

 4. Define greatest lower bound in Poset.

 5. Write the least upperbound and gratest lower bound of the set {3, 5} in the poset < Z - {0}, ≤ >  where ≤ is the divides relation.

 6. Is the relation R = (< x, y > /x ≥ y) antisymmetric ? Justify.

 7. Define a Hamiltonian Graph.

 8. Briefly explain spanning tree.

 9. What is mean by chromatic number of a graph ?

 10. Define cut vertices and cut edge.

 11. Write the matrix representation of the graph.

 12. Write the definition of incidence matrix:

[  2  x 10 =  20 ]

 Section B (Short Essay Type Questions)

 Answer all questions, each correct answer carries a maximum. of 5 marks.

 Ceiling 30 marks.

 13. Show that for any two sets A and B, A - (A ⋂ B) = A - B.

 14. Explain set operations with Venn diagram.

 15. Write the Boolean expression  x₁⊕ x₂ in  an equivalent sum of products canonical form in three variables x_1,x_2,x₃:

 16. Is the "divides" relation a partial ordering on the set of non zero integers ? Explain.

 17. Define complete graph. Show that complete graph with n nodes has the maximum number of edges n (n - 1 )/2.

 18. Define planar graphs. Is k_3,3 a planer graph ? Justify.

 19. Explain Depth-first search Algorithm for spanning tree.

[  5  x  6 =  30  ]

 Section C (Essay Type Questions)

 Answer any one question, correct answer carries 10 marks.

20. Show that < B, *,⊕,' 0,1 > is a Boolean Algebra. Also explain the properties.

 21. Draw the breadth first search spanning tree of the following graph. Explain the algorithm with this example.

[  1   x  10   =  10  ]