Discrete Mathematics
CSE · Final · Spring 22
Section All
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)}