Discrete Mathematics
CSE · Final · Fall 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
Faculty of Science & Information Technology
Final Examination, Fall 2022
Course Code: CSE131, Course Title: Discrete Mathematics
Sections & Teachers: All
Time: 2:00 Hrs
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. a) Discover the shortest path using Dijkstra's algorithm. Explain the step by step solution on your own. [Figure: a weighted graph with vertices labeled s, v1, v2, v3, v4, t and edge weights] | 5 | CO3
1. b) Determine whether following graph has Euler Circuit or not? [Figure: a graph with vertices A, B, C, D, E, F, G and edges connecting them] | 5
2. a) On your trip to a country, you plan to visit all the important world heritage sites but are short on time. To make your itinerary work, you decide to use an algorithm to determine your visiting plan. Consider the nodes of the following graph as the world heritage sites and the edges indicate the distance between two adjacent sites. [Figure: a table or graph showing sites a, b, c, d, e, f and distances] | 5 | CO3
2. b) Simplify the graph as your requirement using the Kruskal algorithm showing all steps sequentially. | 5
3. b) Show which pairs of following graphs are isomorphic, if two pairs are not isomorphic explain why. [Figure: three graphs labeled G, H, and K with vertices and edges] | 5
3. a) Let A be the adjacency matrix of a weighted graph, G, with the columns and rows labeled, in order, by the vertices of the set V = {v0, v1, v2, v3, v4, v5} so the first row of the matrix represents the adjacencies of vertex v0, the second row those of vertex v1, etc. Note that there are some non-zero diagonals which means that there are some edges of the form (v, v). Also, an entry with weight 0 means there is no edge.
A = [0 1 3 0 0 2; 1 1 0 4 5 0; 3 0 0 5 4 0; 0 4 5 2 0 6; 0 5 4 0 0 7; 0 0 0 6 2 3]
(i) Find the adjacency lists for the graph, such that the edges in each list are ordered by increasing weight. | 3+2 | CO3
(ii) Construct the equivalent graph from the given adjacency matrix representation.
3. b) Determine whether following graphs are bipartite or not [Figure: four graphs labeled H, G, etc.] | 5
4. a) Let R be the relation on a set {a, b, c, d, e} containing the ordered pairs {(b,c), (b,e), (c,e),(d,a),(c,b) and (e,e)}. Find the transitive closure of R. | 5 | CO2
4. b) (b) Let R be the relation on a set {4, 5, 6, 7} containing the ordered pairs (4, 5), (5, 5), (5, 6), (6, 4), (6, 6) and (7, 4). Discover the symmetric and reflexive closures of R. | 5