Title 3140708 - DM 2020S.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER– IV EXAMINATION – SUMMER 2020 Subject Code: 3140708 Date:29/10/2020 Subject Name: Discrete Mathematics Time: 10:30 AM TO 01:00 PM Total Marks: 70 Instructions: 1. Attempt all questions. 2. Make suitable assumptions wherever necessary. 3. Figures to the right indicate full marks. Marks Q.1 (a) If A = {a, b} and B = {c, d} and C = {e, f} then find (i) (A B)U(B C) (ii)A (BUC). 03 (b) Define even and odd functions. Determine whether the function   f : I R defined by f (x0  2x  7 is one-to-one or bijective. 04 (c) (i) Show that the relation x  y(mod m) defined on the set of integers I is an equivalence relation. 03 (ii) Draw the Hasse diagram for the partial ordering {(A, B)/ A  B} on the power set P(S) , where S  {a,b,c}. 04 Q.2 (a) Define equivalence class. Let R be the relation on the set of integers I defined by ( x – y ) is an even integer, find the disjoint equivalence classes 03 (b) A committee of 5 persons is to be formed from 6 men and 4 women. In how many ways can this be done when (i) at least 2 women are included (ii) at most 2 women are included ? 04 (c) Solve the recurrence relation 2 an  5an1  6an2  3n using the method of undetermined coefficients. 07 OR (c) Solve the recurrence relation using the method of generating function 5 6 3 , 2; 0, 2. a  a 1  a 2  n  a0  a1  n n n n 07 Q.3 (a) Define simple graph, degree of a vertex and complete graph. 03 (b) Define tree. Prove that there is one and only one path between every pair of vertices in a tree T. 04 (c) (i) A graph G has 15 edges, 3 vertices of degree 4 and other vertices of degree 3. Find the number of vertices in G. 03 (ii) Define vertex disjoint and edge disjoint subgraphs by drawing the relevant graphs. 04 OR Q.3 (a) Show that ( , ) G 5 is a cyclic group, where G={ 0, 1, 2, 3, 4 }. 03 (b) Define the following by drawing graphs (i) weak component (ii) unilateral component (iii) strong component. 04 (c) (i) Construct the composite tables for (i) addition modulo 4 and (ii) multiplication modulo 4 for {0,1,2,3} Z4  . Check whether they have identity and inverse element. 03 (ii) Define ring. Show that the set               a b R b a M / , 0 0 is not a ring under the operations of matrix addition and multiplication. 04