Skip to content

Discrete Mathematics

CSE · Final · Spring 22

Section All

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

Read the questions as text

Read off the PDF by AI, so it may have mistakes. The PDF is the original.

Daffodil International University Department of Computer Science and Engineering Faculty of Science & Information Technology Final Examination, Semester: Spring - 2022 Course Code: CSE 131 (DAY), Course Title: Discrete Mathematics Section: All, Course Teachers: All Time: 2 hours Marks: 40 [Answer all of the following questions. You must answer parts of a question sequentially. The figure in the square brace at the right side of a question indicates the marks allocated to the questions. The symbols and notations used to carry their usual meanings.] 1.a) Six friends want to make their houses in such a way that they each can directly go from their house to each of their friends' houses. They also want to make sure that while making their houses there exists a special path among their houses such that if they start travelling from one house, they can return to the same house travelling every path correspondence to their every house only once. Can you help them to solve their problem? If yes, draw a graph as a solution and if not, explain why? [5] CO3 b) Construct a formula to calculate how many complete cycles are possible from a K10 if K10 has only one complete cycle? [5] CO3 2.a) Apply the Dijkstra algorithm to find the shortest path from a to i from the following graph. [5] CO3 [Figure: A weighted undirected graph with vertices a, b, c, d, e, f, g, h, i and various edge weights: (a,b)=4, (a,c)=8, (b,d)=11, (c,d)=2, (c,e)=7, (c,f)=1, (d,g)=2, (e,g)=4, (e,h)=9, (f,g)=6, (g,h)=14, (h,i)=10, (f,i)=2] b) Prove the Handshaking theorem for the graph represented by the following adjacency matrix. [5] CO3 a | b | c | d a | 0 | 2 | 3 | 0 b | 1 | 2 | 2 | 1 c | 2 | 1 | 1 | 0 d | 1 | 0 | 0 | 2 3.a) Apply Prim's algorithm on the following graph to prepare a minimum spanning tree. [5] CO3 [Figure: A weighted undirected graph with vertices a, b, c, d, e, f, g, h, i and edge weights similar to question 2.a] b) Prove whether the following graphs are isomorphic? [5] CO3 [Figure: Two graphs shown side by side. The left graph is labeled with vertices 1 through 10. The right graph is labeled with vertices A through J in a pentagonal arrangement.] 4.a) Identify the properties of the following relations: [5] CO2 i) R1 = {(1, 2), (2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)} ii) R2 = {(1, 1), (1, 4), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4), (4, 4)} b) Identify the transitive closures of the given relation. [5] CO2 R = {(1, 2), (2, 1), (2, 3), (3, 4), (4, 2)}