Engineering BE Computer Engineering Sem 3 December 2022 2022 Discrete Structures And Graph Theory Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 Q.1 is compulsory
2. Q2 Solve any 3 questions out of remaining 5 questions
3. Q3 Assumptions made should be clearly stated
4. Q4 Draw the figures wherever required
5. Q1 Solve any four of the following questions
   • a) Prove using Mathematical Induction that is divisible by 3 for all 5
   • b) Explain the following terms with suitable example: 5
6. Q1 Partition set
   • c) State the Pigeonhole principle and show that if any five numbers from 1 to 8 are chosen, then two of them will add to 9. 5
   • d) Consider the function f(x) = 2x-3. Find a formula for the composition functions 5
   • ii) P=fofof
   • e) Explain the bipartite graph with suitable example. 5
   • a) What is a transitive closure? Find the transitive closure of R using Warshall’s algorithm
   • b) What is a ring? Let A= {0, 1,2, 6,7}. Determine whether a set A with addition modulo 8 & multiplication modulo 8 is a commutative ring? Justify your answer. 10
   • a) A survey in 1986 asked households whether they had a player or cable TV. 40 had a VCR. 60 had a CD player; and 50 had cable TV. 25 owned VCR and CD player. 30 owned a CD player and had cable TV. 35 owned a VCR and had cable TV. 10 households had all three. How many households had at least one of the three? How many of them had only CD
   • b) Find the complete solution of a recurrence relation 6 an +2an-1 = n+ 3 for and with ao =3
   • c) Obtain CNF & DNF for the following expression: 6
   • a) What is a group? Let A={3, 6 ,9, 12} 10
7. Q1 Prepare the composition table w.r.t. the operation of multiplication modulo 15 marks
   • ii) Whether it is an abelian group? Justify your answer
   • iii) Find the inverses of all the elements
   • iv) Whether it is a cyclic group?
   • b) What are the isomorphic graphs? Determine whether following graphs are isomorphic. 10
   • a) Let X={1, 24, 36} & R| x divides y} 10
8. Q1 Write the pairs in a relation set R 1i) Construct the Hasse diagram What are the Maximal and Minimal elements?
   • iv) Mention Chains and Ant chains from above set
   • v) Is this poset a lattice?
   • b) Define the term bijective function. 5 Let (7/5) >R be defined by f(x) = Whether a function is bijective? Justify your answer
   • c) Define minimum hamming distance. Consider e : Find the code words generated by the parity check matrix H given below. 5
   • a) Define with example Euler path, Euler circuit, Hamiltonian path, and Hamiltonian circuit Determine if the following diagram has Euler circuit and Hamiltonian circuit. Mention the
   • b) Let p denote the statement ‘The food is good’, q denote the statement “The service is good’ & r denote the statement ‘The rating is 3 star.’ Write the following statements in a symbolic form- 8
9. Q1 Either food is good or service is good or both li) The food is good but service is not good ili) If both food & service are good then the rating is 3 star
   • iv) It is not true that a 3 star rating always means good food & good service
   • c) Find out the incidence matrix of following graphs. 6

Read from the scan above, so a character or two may differ. The scan is the original.