**Roll No……..**

**Total No. of Questins:9]**

**B.Tech. (Sem. – 3**

^{rd})**DISCRETE STRUCTURES**

**SUBJECT CODE : CS - 203**

**Paper ID : [A0452]**

**Time : 03 Hours**

**Instruction to Candidates:**

1) Section - A is Compulsory.

2) Attempt any Four questions from Section - B.

3) Attempt any Two questions from Section - C.

**Section - A**

l.

(a) Show that the sum
of the degrees of the vertices of a non directed graph is twice the number of edges in the graph.

(b) Define the terms (i) Regular graph (ii) Complete graph

(c) Give an example of a graph that has neither an Euler
circuit nor a Hamiltonian circuit.

(d) Define a tree.

(e) Define an equivalence relation and give an example of
the same.

(f) If a
a
G , where G is a group, then show that G is commutative.

^{-1}= a
(g)
a,b
R
where R is a ring, show that (-a).(-b) = a.b

(h) Every field is an integral domain. Give an example to
establish that the converse is not true.

(i) In a Boolean algebra B, show that, a + a = a
a
B.

(j) What is the generating function for the sequence S
0
?

_{n}= ba^{n},n**Section -B**

2. Among the first 1000 positive integers:

(a) Determine the integers which
are neither divisible by 5, nor by 7, nor

by 9.

(b) Determine the integers
divisible by 5 but not by 7, not by 9.

3 Solve the recurrence relation S(K) - 4S (K -1 ) + 3 S (K -
2) K

^{2}, without using the concept of generating functions.
4 Let R be the relation on the set of ordered pairs of
positive integers such

that (a,b) R (c,d) if and only if
a+d = b+c. Show that R is an equivalence relation.

5. State and prove the Lagrange’s theorem.

6. Consider the Boolean function, f(x,y,z) = (x.y + z).(x’ + y.z’).(x’+ z) Construct the circuit
corresponding to the Boolean function of the Boolean
algebra of switching circuits.

**SECTION-C**

7. Show that every field is an integral domain.

8. Consider any connected planar graph G=(V,E) having R
regions,

V vertices and E edges. Show that
V+R-E = 2.

9. Find the generating function from the recurrence relation

S(n - 2) = S(n - 1) + S(n) where
S(0) = S(l) =1, n
0.

## 0 comments:

Post a Comment