Download SGBAU BCA 2019 Summer 2nd Sem DIscrete Mathematics Question Paper

Download SGBAU (Sant Gadge Baba Amravati university) BCA 2019 Summer (Bachelor of Computer Applications) 2nd Sem DIscrete Mathematics Previous Question Paper

AW-l797
B.C.A. (Part?I) Scmcster?ll Examination
ZSTS : DISCRETE MATHEMATICS
Timc : Three Hours] [Maximum Marks : 60
Note :?(1) All questions cany equal marks.
(2) All questions are compulsory.
1. (3) Explain the following terms :
(1) Paralleledges
(ii) Loop
(iii) Pendent vertex. 6
(b) Define connected and disconnected graph and give the example of graph which gets disconnected
on removing one edge. 6
0R
2. (a) De?ne the following terms with suitable example :
(i) Bipartitc graph
(ii) Null graph
(iii) ' Finite graph. 6
(b) Explain the following with example :
(1) Union
(ii) Intersection
(iii) Ring sum oftwo graphs. 6
3. .(a) Defmc edge connectivity and vertex connectivity of a graph. Also ?nd the edge connectivity
and vertex connectivity of following graph : 6
v
a ? b
1
/
w t
x ,V? b L
(b) By using Dijkstra?s algorithm ?nd shortest path from vertex 8. to z : 6
YBC?l536l l (Contdl)

4. (a) Prove that vertex connectivity n:? at exceeds edge connectivity. 6
(b) Explain the following terms :
(1) Walk
(1i) Path
(iii) Trail. 6
5. (a) Show that following graph is Eulerian and trace Eulerian circuit by using Fluery?s
algorithm : 6
'\
\
f e
(1)) Find Hamiltonian path and cycle in following graph : 6
Z___ d ,____ d
C (1) c (2) ?
OR
6. (3) Write the characteristics of Eulerian graph in terms of degree.
(b) Show that following graph is Eule?an and ?nd Eulerian circuit :
b
,/1?
/ i \\
"'7 C
/T\
7. (3) Find the centre and radius offo?owing trcc : 6
\ C J
\: / g I
/ V d I i
c ? f h
(b) Prove that a binary tree of n vewticcs has (n + 1)/2 pendent vcrticcs. 6
OR
YBC?1536l
IJ
(C ontd.)

V 8. (a) De?ne the following with suitable example :
(i) Spanning Tree
(ii) Fundamental Circuit
(iii) Fundamental Cutsct.
(b) De?ne binary tree and prove that binary tree has odd number of vertices.
9. (a) Explain the different types of directed graphs with suitable example.
(b) De?ne the following :
(i) Arborescence
(1i) Network
(iii) Diagraph.
OR
10. (a) Find the shortest spanning tree by using Kruskal?s algorithm :
cl(10)
a
c?(IO) 99$ e (5)
d
c,(15) c
(b) Prove that every connected graph has at least one spanning tree.
YBC?l5361 3