**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**

QI)

a) What do you mean by chromatic
number?

b) Define Euler graph.

c) Define Semi-group.

d) Write down DeMorgan's law for
set.

e) Check whether Relation I of
divisibility on the set N of positive integers

is an equivalence relation or not? Justify
your answer.

f)Find Chromatic number for
bipartite Graph (Kr, r).

g) Postfix expression for the infix
expression A+B * (C+D)/F+D * E is....

h) Write down the inclusion and
exclusion principle on sets.

i) Define ring with example.

j) Find the multiplication table
for G: { l, 2,3,4,5, 6} under multiplication

modulo 7.

**Section - B**

Q2) What do you mean by cyclic group? Show that any subgroup
of a cyclic group is cyclic.

Q3) Solve the recurrence relation, a

_{n}= 3a_{n-1 }+10a_{n-2}, n2, given a_{0}= 1, a_{1}=-4.
Q4) (a) Using Graph Representation of a relation how we can
identify that a Relation is
Reflexive, symmetric and anti-symmetric.

(b) Let X: {1, 2,3,4,5,6,7} and R: {(x, y)x -y is divisible by 3} Check whether this equivalence
Relation or riot? Give appropriate

reason in support of your answer?

Q5) Give an example of a graph and explain for the following
:

(a) A Graph is having Hamiltonian
and Euler Circuit.

(b) A Graph is having Hamiltonian
Circuit but not an Euler Circuit.

(c) A Graph is having Euler Circuit
but not an Hamiltonian Circuit.

Q6) How many integer S between 1 and 300 (inclusive) are

(a) Divisible by at least one of 3,
5,7?

(b) Divisible by 3 and 5, not by 7.

(c) Divisible by 5 but neither by 3
or 7?

**Section - C**

Q7) Define the following terms with help of example

(a) Ring

(b) Fields.

Q8) Consider the group G : { I, 2, 3, 4, 5) under
multiplication modulo 6.

(a) Find the multiplication table
of G.

(b) Prove that G is a group.

(c) Find 2-r,3-t and 1-r.

(d) Find the orders and subgroups
generated by 2 and 3.

(e) Is G cyclic. Justify your answer.

Q9) (a) Let G : (V
E) be an undirected graph with k-components and lVl : n,

lEl: m. Prove that m> n - k .

(b) Explain any two applications of
Coloring of a Graph.

## 0 comments:

Post a Comment