Title 3140708 - DM 2023S.pdf ✅

1 Seat No.: ________ Enrolment No.___________ GUJARAT TECHNOLOGICAL UNIVERSITY BE - SEMESTER– IV(NEW) EXAMINATION – SUMMER 2023 Subject Code:3140708 Date:17-07-2023 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. 4. Simple and non-programmable scientific calculators are allowed. Q.1 (a) If  3 , 6,  n A x x n n N = =    9 , 4,  n B x x n n N = =   then find A B, A B and A B− . 03 (b) Check whether the relation R defined in the 1,2,3,4,5,6 as R a b b a = = + ( , : 1 )  is reflexive, symmetric or transitive. 04 (c) (I) Prove that p q → and ( ) p q  are logically equivalent. 03 (II) Let   2 Y n n N =  : and f N Y : → defined as 2 f n n ( ) = . Show that f is invertible and find the inverse of f . 04 Q.2 (a) In a survey of 400 students in a school, 100 were found as drinking apple juice, 150 as drinking orange juice and 75 drinking both apple and orange juice. Find how many students drink neither apple nor orange juice. 03 (b) Let f R R : → be function defined by f x ax b ( ) = + . Find values of a and b for which R f f I = 04 (c) If R a b a b = − = ( , : 1 )  and S a b a b is even = − ( , :)  be two relations on A ={1,2,3,4} . Then (I) Find matrices of R and S , (II) Find digraph of R and S (III) Find the relation RS 07 OR (c) (I) Find n if 2 3 3 3 n n n C C P + + = 03 (II) From 4 professors and 6 students, a committee of 3 is to be formed. In how many ways, this can be done, if the committee contains (1) at most 1 professor (2) at least 2 professors. 04 Q.3 (a) Find reachable set of all the vertices and node base of following graph. 03
2 (b) Show that in a lattice if abc   , then (I) a b b c  =  and (II) ( ) ( ) ( ) ( ) a b b c b a b a c    = =    04 (c) Solve the recurrence relation which represents the Fibonacci sequence F F F n n n = + − − 1 2 with F F 0 1 = =1. 07 OR Q.3 (a) The Indian cricket team consist of 16 players. It includes 2 wicket keepers and 5 bowlers. In how many ways eleven player can be selected if we have to select on wicket keeper and at-least 4 bowlers? 03 (b) Prove that any graph has even number of odd vertices. 04 (c) Find the generating function of a a a n n n + + 2 1 = + , where 0 1 a a = =1 for n  1 07 Q.4 (a) If G is an abelian group with n elements 1 2 , ,....., g g gn then show that ( ) 2 1 2..... n g g g e = , where e is the identity element of G 03 (b) Draw a binary tree whose post-order produced the string d g e b i j h f c a − − − − − − − − − and pre-order produces the string j b a c d i h e g f − − − − − − − − − 04 (c) Define Lattice. And draw the Hasse diagram representing the partial ordering ( , ) : A B A B   on the power set P S( ) where S ={1,2,3} . Find the maximal, minimal, greatest and least elements of the poset. 07 OR Q.4 (a) Define Isolated vertex, Pendent vertex and Size of a graph 03 (b) Let G be a graph with n vertices and m edges such that vertices have degree k or k +1 . Prove that if G has vertices of degree and Nk+1 vertices of degree k +1 then N k n m k = + − ( 1) 2 04 (c) Show that G is an abelian group under usual matrix addition, where , , , a b G a b c d R c d         =                07 Q.5 (a) Show that the only right coset of a subgroup H in a group G that is also subgroup of G is H itself. 03 (b) Dose there exists a 4- regular graph with 6 vertices? If so, construct the graphs. 04 (c) Show that ( , , ) R +  is an integral domain, where R a b a b I = +   5 ,  07 OR Q.5 (a) Define cycle, walk and tree. 03 (b) Find transitive closure by Warshall’s Algorithm if A ={1,2,3,4,5} and R ={ 1,2 , 3,4 , 4,5 , 4,1 , 1,1 } ( ) ( ) ( ) ( ) ( ) 04 (c) Define Isomorphic Graphs. Determine whether the following graphs are isomorphic or not. 07 Nk k
3