Discrete Mathematics B.C.A 18-21 Sem 2 - Second Internal April 2019

SAINTGITS COLLEGE OF APPLIED SCIENCES

SECOND INTERNAL ASSESSMENT EXAMINATION, APRIL 2019

Department of Mathematics, Semester 2

DISCRETE MATHEMATICS II

                                                          ANSWER KEY      

Section A

1.Simple graph that contains exactly one edge between each pair of distinct vertices. Give example

2.Yes. Give reason

3. Draw graph

4. Definition with example

5. If G is a simple graph with n vertices such that degree of every vertex in G is at least n/2, then G has

   a Hamilton path

6. Definition with example

7.                          +

                                 /

                  +       2  -       3

                           4

8.

0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

9. )

10. Definition with example

11. Definition with example

12.  2

                                                                                                                        (10 X 2 = 20 marks)

Section B

Answer any 6 questions. Each question carries 5 marks.

13. Write proof

14. Explanation with graph

15. Write proof

16. 8

17.Write algorithm

18. +  +

19.

0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

20. Normal form is  and rank is 2

21. Give proof

(6 X 5 = 30marks)

Section C

Answer any 2questions. It carries 15marks.

22.a) Give algorithm

      b) Give explanation with figure

23. Preorder –   a, b, d, e, I, j, m, n, o, c, f, g, h, k, l, p

     Inorder –   d, b, i, e, m, j, n, o, a, f, c, g, k, h, p, l

    Postorder  -  d, i, m, n, o, j, e, b,  f, g, k, p, l, h, c, a

24. Draw circuits

25.a)   

    b)