Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2013

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2013
GS-6525 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Figures to the right indicate marks.
	(6)	Assume suitable data if necessary.
1.	(a)	Prove the mathematical Induction --- 12 + 22 +32+ ......n2 = n(n+1) (2n+1)/6.	08
	(b)	Explain the terms :-      (i) Poset      (ii) Normal Subgroup      (iii) Lattice.	06
	(c)	In a survey of 60 people, it was found that 25 reads Newsweek Magazine, 26 reads Times and 26 reads Fortune. Also 9 reads both Newsweek and Fortune, 11 reads both Newsweek and times, 8 reads Time and Fortune and 8 reads no magazine at all.      (i) Find the number of people who read all three magazines.      (ii) Determine number of people who read exactly one magazine.	06
2.	(a)	Define injective, surjective and bijective functions. if f : R→R and g : R → R are defined by the formulas --        f(x) = x + 2 and g(x) = x2  Find     (i) f.g.f     (ii) g.f.g.	08
	(b)	Define equivalence relation on a set. Let R be a relation on the set of integers defined by aRb iff a-b is a muliple of 5. Prove that R is a equivalence relation.	06
	(c)	State the converse, inverse and contrapositive of the following :-      (i) If it is cold, then he wears a hat.      (ii) If an integer is a multiple of 2, then it is even.	06
3.	(a)	Explain Hasse diagram. Draw the Hasse diagram of the relation given by :--     (i) R1= { (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5),                   (3, 3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5) }    (ii) R2= { (1, 1), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5),                   (3, 3), (3, 4), (3, 5), (4, 4), (5, 5) }	08
	(b)	Let A = {1, 2, 3, 4} and R = { (1, 2), (2, 3), (3, 4), (2, 1)}. Find the Transitive closure or R using Warshall's Algorithm.	06
	(c)	Consider the region shown below. It is bounded by a regular hexagon whose sides are the length 1 units. Show that if any seven points are chosen in this region then two o them must be no further apart than 1 unit.	06
4.	(a)	Show that the following graphs are isomorphic.	08
	(b)	Let R = {(1, 2), (4, 3), (2, 2), (2, 1), (3, 1)} be a relation on s = {1, 2, 3, 4}. Find the symmetric closure of R.	06
	(c)	Define :      (i) Integral domain      (ii) Field      (iii) Normal Subgroup.	06
5.	(a)	What is minimum spanning tree? Explain any one technique with example.	08
	(b)	Define Cyclic Group. Prove that the set A = {0, 1, 2, 3, 4, 5} is a finite abelian under addition modulo 6.
	(c)	Determine whether the given graph has a Hamilton circuit or Eulerian circuit. If it does, find such a circuit.