C33337
C 33337
FIRST SEMESTER B.C.A DEGREE EXAMINATION, NOVEMBER 2017
(CUCBCSS-UG)
Complementary Course
BCA 1C 02 DISCRETE MATHEMATICS
Time : Three Hours Maximum 80 Marks
Part A (Objective Type)
Answer all the ten questions.
Each question carries 1 mark.
1. What do you mean by a proposition
2. Write the negation of the statement 'all people are intelligent'.
3. If |A| = 10 then |P(A) =....................,
4. Draw the graph Kg3,2
5. A closed path is called a........................,
6. State Euler's formula for plane graph.
7. Assign a truth value for the statement 6 + 4 = 10 Λ 0 < 2.
8. Give an example of a 2 regular graph.
9. What do you mean by a cut vertex ?
10. What can you say about sets A and B if A ⋂ B = B
(10 x 1 = 10 marks)
Part B (Short Answer Type)
Answer all five questions.
Each question carries 2 marks.
11. Construct a truth table for ~ pΛ ~ q.
12. Give an example of a relation which is reflexive and transitive but not symmetric.
13. Define isomorphism of two graphs.
14. Define bipartite graph.
15. What do you mean by a self complimentary graph ? Give an example.
(5 x 2 = 10 marks)
Part C (Short Essay)
Answer any five questions.
Each question carries 4 marks.
16. Define a boolean algebra.
17. Show that [(pvq)⇒ r ]^(~ P)⇒(g⇒r) is tautology without using truth tables.
18. Prove that in a tree every vertex of degree greater than one is a cut vertex.
19. Prove that every connected graph contains a spanning tree.
20. Let G be a graph in which the degree of every vertex is at least 2. Show that G contains a circuit.
21. Find the power set of each of these sets:
(a) ф; (b) {ф}:
(c) { ф,{ ф}}: (d) {a, b}.
22. Show that in any group of two or more people, there are always two with exactly same number of friends inside the group.
23. Prove that a connected graph G is a tree if and only if every edge of G is a cut edge of G.
(5 x 4 = 20 marks)
Part D
Answer any five questions.
Each question carries 8 marks.
24. (a) Write the disjunctive normal form of : p⇒ ((p⇒ q)^ ~ (~ qv ~ p).
(b) Write the conjunctive normal form of: (qv(pvr))^~((pvr)^q).
25. Give a short note on traveling salesman problem.
26. Prove that a connected graph G with at least two vertices contains at least two vertices that are not cut vertices.
27. Prove that a graph has a dual if and only if it is planar.
28. Show that G is Euler if and only if every vertex of G is even.
29. Write short notes on (a)network; (b)Max-flow min-cut theorem.
30. Prove that a graph is bipartite if and only if it contains no odd cycles.
31. If G in a simple graph such that d(v)≥n/2 for all vertices v of G, then show that G in Hami Honian.
(5 x 8 = 40 marks)
നിങ്ങൾക്ക് ഉപകാരപ്പെട്ടെങ്കിൽ നിങ്ങളുടെ കൂട്ടുകാർക്ക് കൂടി ഷെയർ ചെയ്യുക
Share This
