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

FirstRanker.com

B.C.A. (Part—I) Semester—II Examination

2ST5 : DISCRETE MATHEMATICS

--- Content provided by FirstRanker.com ---

Time : Three Hours] [Maximum Marks : 60

Note :— (1) All questions carry equal marks.

(2) All questions are compulsory.

1. (a) Explain the following terms :
   1. Parallel edges
   2. Loop

   --- Content provided by FirstRanker.com ---

   3. Pendent vertex. 6
   (b) Define connected and disconnected graph and give the example of graph which gets disconnected on removing one edge. 6
2. (a) Define the following terms with suitable example :
   1. Bipartite graph
   2. Null graph
   3. Finite graph. 6

   --- Content provided by FirstRanker.com ---

   (b) Explain the following with example :
   1. Union
   2. Intersection
   3. Ring sum of two graphs. 6
3. (a) Define edge connectivity and vertex connectivity of a graph. Also find the edge connectivity and vertex connectivity of following graph : 6

   [Graph Description]

   --- Content provided by FirstRanker.com ---

   (b) By using Dijkstra’s algorithm find shortest path from vertex a to z : 6

   [Graph Description]

4. (a) Prove that vertex connectivity. 6 (b) Explain the following terms :
   1. Walk
   2. Path
   3. Trail. 6

   --- Content provided by FirstRanker.com ---

5. (a) Show that following graph is Eulerian and trace Eulerian circuit by using Fluery’s algorithm : 6

   [Graph Description]

6. (a) Write the characteristics of Eulerian graph in terms of degree. (b) Show that following graph is Eulerian and find Eulerian circuit :

   [Graph Description]

--- Content provided by FirstRanker.com ---

7. (a) Find the centre and radius of following tree : 6

   [Tree Description]

   (h) Prove that a binary tree of n vertices has (n + 1)/2 pendent vertices. 6
8. (a) Explain the following terms :
   1. Spanning Tree
   2. Fundamental Circuit
   3. Fundamental Cutset.

   --- Content provided by FirstRanker.com ---

   (b) Define 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) Define the following :
   1. Arborescence
   2. Network
   3. Diagraph.

--- Content provided by FirstRanker.com ---

10. (a) Find the shortest spanning tree by using Kruskal’s algorithm :

    [Graph Description]

    (b) Prove that every connected graph has at least one spanning tree.

FirstRanker.com