Download AKTU B-Tech 3rd Sem 2016-2017 NCS 302 Discrete Structures And Graph Theory Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2016-2017 NCS 302 Discrete Structures And Graph Theory Question Paper

Printed .Pages: 4 NCS-302
(Following Paper ID and Roll No. to be ?lled in your
Paper ll) : 2 . . Roll No.
Answer Books)
B.TECH.
Regular Theory Examination (Odd Sem-III), 2016-17
DISCRETE STRUCTURES AND GRAPH
THEORY
T ime : 3 Hours Max. Marks : 100
SECTION -A
Attempt all parts. All parts carry equal marks. Write
answer of each part in short. (10X2=20)
1. a) Let R be a relation on the set of natural numbers N,
b)
d)
as R = {(x,y): x,y e N, 3x +y = 19}. Find the
domain and range of R. Verify whether R is,
re?exive.
Show that the relation R on the set Z of integers
given by R = {(a,b): 3 divides a ? b}, is an
equivalence relation.
Show the implications without constructing the
truth table (P? > Q)? > Q=> PvQ.
Show that the ?greater than or equal? relation (>=)
is a partial ordering on the set of integers.
302/12/2016/15480 (1) [P.T.O.

NCS-302
e) Distinguish between bounded lattice and
complemented lattice.
f) F ind the recurrence relation from y" = A2" + B(?3)".
g) De?ne ring and give an example of a ring with zero-
divisors. ? '
h) State the applications of binary search tree.
i) De?ne Multigraph. Explain with example in brief.
j ) Let G be a graph with ten vertices. If four vertices
has degree four and six vertices has degree ?ve, then
?nd the number of edges of G
SECTION - B
Attempt any 5 questions from this section
(5X 10:50)
Write the symbolic form and negate the following
statements :
0 Everyone who is healthy can do all kinds of work.
? Some people are not admired by everyone.
- Everyone should help his neighbors, or his neighbors
will not help him.
In a Lattice if aSbSc , then show that
a) avb=bAc
b) (avb)v(bAc)=(avb)/\(avc)=b
302/12/2016/15480 (2)
10.
NCS-302
State and prove Lagrange?s theorem for group. Is the
converse true?
Prove that a simple graph with n vertices and k
(n?k)(n?k+l)
2 edges.
components can have at most
1 l l n
Prove by induction: E+?3+ ----- + "(n +'T) ='(?n +1) .
Solve the recurrence relation y?+2 ? Sym + 6y? = 5"
subject to the condition yo = 0, y1 = 2.
a) Prove that every ?nite subset of a lattice has an LUB
and a GLB.
b) Give an example of a lattice which is a modular but
not a distributive.
Explain in detail about the binary tree traversal with an
example.
SECTION - C
Attempt any 2 questions from this section.
(2 x l 5=30)
a) Prove that a connected graph G is Euler graph if
and only if every vertex of G is of even degree.
302/12/2016/15480 (3) [P.T.O.

NCS-302
b) Which of the following simple graph have a
Hamiltonian circuit?or, if not a Hamiltonian path?
a b a b a b g
e C 1
d Zc
: . d c e f
d
91 62 63
11. a) Find the Boolean algebra expression for the
following system.
OED}
b) Suppose that a cookie shop has four different kinds
of cookies. How many different ways can six
cookies be chosen?
12. a) Prove that every cyclic group is an abelian group.
b) Obtain all distinct left cosets of {(0), (3)} in the
group (Z6, +6) and ?nd their union.
c) Find the left cosets of { [0], [3]} in the group (Z6, +6).
++++
302/12/2016/15480 (4)