Skip to content

Discrete Mathematics

CSE · Final · Spring 24

Batch 64

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 Faculty of Science & Information Technology Department of Computer Science and Engineering Final Examination, Spring-2024 Course Code: CSE212 Course Title: Discrete Mathematics Level: 2 Term: 1 Batch: 64 Exam Duration: 02 Hours Marks: 40 Answer ALL Questions [The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.] 1. Consider the following adjacent matrix where a, b, c, d, e and f are the vertices of an undirected graph. | a | b | c | d | e | f a | 1 | 1 | 3 | 0 | 0 | 0 b | 1 | 0 | 2 | 2 | 0 | 9 c | 3 | 2 | 0 | 1 | 0 | 3 d | 0 | 2 | 1 | 0 | 9 | 1 e | 0 | 0 | 0 | 9 | 0 | 1 f | 0 | 9 | 3 | 1 | 1 | 0 a) Construct a graph from the given matrix. [2] b) Prove handshaking theorem for the graph. [3] c) Prove whether the following graphs G and H are isomorphic or not? [5] [Figure: Graph G with vertices 1, 2, 3, 4, 5, 6 and Graph H with vertices a, b, c, d, e, f] 2. Derive a relation from the graph and find whether the relation is reflexive, symmetric, antisymmetric and transitive. If not make at least one relation putting the pair which are needed. [5] [Figure: A directed graph with vertices 1, 2, 3, 4, 5, 6, 7, 8, 9 and weighted edges] Prove that 2 - 2.7 + 2.7^2 - ... + 2.(-7)^n = (1 - (-7)^(n+1)) / 4 whenever n is a nonnegative integer. [5] 3. Draw the following graphs and also find out the degree of each vertices of the graphs. [5] i. K_4,7 ii. W_5 b) Apply coloring algorithm to show whether the graphs are bipartite or not. [5] [Figure: Graph A and Graph B] 4. Suppose that the nodes of Graph G are {a, b, c, d, e, g, h} and the weights of the edges in G are given in the following matrix. Here, the symbol (*) when there is no edge between a given pair nodes. | a | b | c | d | e | f | g | h a | 0 | 4 | 5 | * | 1 | 2 | 1 | 5 b | 4 | 0 | 1 | 3 | * | 1 | 8 | 15 c | 5 | 1 | 0 | 9 | 2 | * | 4 | 7 d | * | 3 | 9 | 0 | 8 | 2 | 4 | 6 e | 1 | * | 2 | 8 | 0 | * | * | 10 f | 2 | 1 | * | 2 | * | 0 | 5 | 8 g | 1 | 8 | 4 | 4 | * | 5 | 0 | * h | 5 | 15 | 7 | 6 | 10 | 8 | * | 0 a) Now, Apply Prim's algorithm, starting at node a, to construct a minimum spanning tree and find the weight based on the given matrix. [5] b) Apply Dijkstra on this weighted graph to find the shortest path from a to h. [5]