## Discrete Structures Question Paper of 3rd Semester CSE74 Download Previous Years Question Paper 7

• Thursday, September 08, 2016
• • ,
• No comments

Roll No……..
Total No. of Questins:9]
B.Tech. (Sem. – 3rd )
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
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, an = 3an-1 +10an-2, n 2, given a0= 1, a1=-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

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.

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.