4 week 12-week 14 Student Full Name:___________________________________ . Student ID:__________________________________________ . CRN No:____________________________________________ . Branch: _____________________________________________. Discrete Mathematics (Math 150) Total Points True/False ____/6 MCQ ____/6 Short Answer ____/18 Total ____/30 Good Luck Discrete Mathematics (Math 150) Marks- 30 Answer all the Questions. Section-I State whether the following statements are True or False. (6 marks, 1 Mark Each) 1. 2. 3. 4. 5. 6. 1 0 1 The relation R represented by the matrix = [1 1 0] is reflexive 0 1 1 and anti-symmetric. The Relation ( ; , ) is a partial ordering on the set A= {1,2,3,4}. A pseudograph may include loops, as well as multiple edges connecting the same pair of vertices. If T is a full binary tree and has 5 internal vertices then the total vertices of T are 13. An undirected graph is called connected if there is a path between every pair of vertices. A 2-dimensional hypercube or 2-cube (Q 2 ) is bipartite. 1 2 3 4 5 6 Section-II (Multiple Choice Questions) (6 marks, 1 Mark Each) 1. A binary relation R is called Partial order relation if A. It is Reflexive and transitive B. It is symmetric and transitive Page 2 of 5 C. It is reflexive, symmetric and transitive D. It is reflexive, anti symmetric and transitive 2. How many relations are there on a set A=(0,1,2...,7) 2 A. 27 2 B. 28 C. 28 D. 27 Use the following directed graph to answer questions 3 and 4: 3. The in-degree of a vertex d or deg(d): A. 1 B. 2 C. 3 D. 0 4. + () is equal to A. 6 B. 7 C. 5 D. 2 5. The longest path of a tree is called A. Vertex B. Edges C. Radius D. diameter 6. A sub graph of a graph G that contains every vertex of G and is a tree is called A. Trivial tree B. empty tree C. Spanning tree D. Full bianary tree MCQ 1 Answers 2 3 4 5 Page 3 of 5 6 Section -III Answer the following Essay Type Questions Each) (18 marks, 3 Mark 1. Let A = {1, 2, 3, 4}, and R is a relation defined by \"a divides b\". Write R as a set of ordered pair and represent it by matrix. 2. Draw the graph of the relation R, represented by adjacency matrix 0 0 1 1 = [1 1 1 0] on set A={1,2,3,4}. By using this graph, show 1 0 1 0 1 0 1 0 that R is not reflexive, not symmetric and not antisymmetric. 3. What are the degrees and neighborhoods of the vertices in the following graph ? 4. State the Handshaking theorem and verify it for the following undirected graph Page 4 of 5 5. Answer the questions for the following tree with root a. b. c. d. e. Find the levels of vertices d and f What is the height of the tree? Which vertices are internal? Which vertices are leaves? Above tree is balance tree 6. Find the spanning tree of following simple graph: Page 5 of 5