D52772
D 52772
FIRST SEMESTER B.C.A. DEGREE EXAMINATION, NOVEMBER 2018
(CUCBCSS-UG)
Complementary Course
BCA 1C 02 DISCRETE MATHEMATICS
(Common for 2014 and 2017 Admissions)
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 connectives ?
2. Draw a simple graph on 4 vertices.
3. Total number of subsets of a set with 12 elements is...................,
4. Write the negation of the statement 'all people are beautiful'.
5. A simple graph in which every vertex is adjacent to all the other vertices is called.......................,
6. State Euler's formula for plane graph.
7. Assign a truth value for the statement 5x = 20 v 0 > 2.
8. Give an example of a 3 regular graph.
9. Define a tree and give an example.
10. What can you say about sets A and B if A ⋂ 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 v q).
12. Give an example of a relation which is reflexive and transitive but not symmetric.
13. Define isomorphism of two graphs.
14. Show that in any graph, the number of vertices of odd degree is even.
15. Draw K, as a planar graph and write the number of faces for this graph.
(5 × 2 = 10 marks)
Part C (Short Essays)
Answer any five questions.
Each question carries 4 marks.
16. Prove that every tree is a bipartite graph.
17. Show that [(pvq) ⇒ r] A (~ P) ⇒ (q⇒r) is a tautology without using truth tables.
18. An edge e = xy of a connected graph G is cut edge of G if and only if e-belongs to no cycle of G.
19. Prove that a simple graph is a tree if and only if any two distinct vertices are connected by a unique path.
20. Let G be a graph in which the degree of every vertex is atleast 2. Then show that G contains a circuit.
21. Find the power set of each of these sets
(a) ф ; (b) (ф);
(c) {ф, {ф}}; (d) {a, b}.
22. If u and v are non-adjacent vertices of a tree T, then T+ uv contains a unique cycles.
23. What do you mean by a boolean algebra.
(5 x 4 = 20 marks)
Part D
Answer any five questions.
Each question carries 8 marks.
24. Prove that a simple cubic connected graph G has a cut vertex if and only if it has a cut edge.
with atleast two vertices contains atleast two vertices that are not
25. Prove that a connected graph G with atleast two vertices contains atleast two vertices that are not cut-vert ices.
26. Prove that every tournament contains a directed Hamiltonian path.
27. Show that G is Euler if and only if every vertex of G is even.
28. Write short notes on :(a) Network ; and (b) Max-flow min-cut theorem.
29. Prove that a graph is bipartite if and only if it contains no odd cycles.
30. Let G be a simple graph with n≥3 vertices. If for every pair of nonadjacent vertices u,v
of G d (u) + d (v)≥n The show that G is Hamiltonian.
31. (a) Write the junctive normal form of :
p⇒((p⇒q) Λ ~ ( pv ~ p)).
(b) Write the conjunctive normal form of :
(qv (p Λ r)) Λ- ((pvr) Λq).
(5 x 8 = 40 marks)
നിങ്ങൾക്ക് ഉപകാരപ്പെട്ടെങ്കിൽ നിങ്ങളുടെ കൂട്ടുകാർക്ക് കൂടി ഷെയർ ചെയ്യുക
Share This
