Fresher Jobs

Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian cities including Bangalore, Chennai, Hyderabad, Pune or Kochi

Resources

Find educational articles, blogs, discussion threads and other resources.

Colleges

Find details about any college in India or search for courses.

Download Model question papers & previous years question papers

Posted Date: 31 Oct 2009 Posted By: Sree.... Member Level: Platinum

2007 Andhra Pradesh State Jawaharlal Nehru Technological University Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 2] Question paper

Course: B.Tech

University: Jawaharlal Nehru Technological University

Code No: RR210501 Set No. 2
II B.Tech I Semester Supplimentary Examinations, November 2007
DISCRETE STRUCTURES AND GRAPH THEORY
( Common to Computer Science & Engineering, Information Technology,
Computer Science & Systems Engineering and Electronics & Computer
Engineering)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks

1. (a) Write the following statement in symbolic form:
“The crop will be destroyed if there is a flood”
(b) Construct the truth table of the following formula.
?(PV(Q ^ R)) ! ((PVQ) ^ (PVR)) [8+8]
2. (a) Show that when a relation R is symmetric, so is any Rk for any k > 0, where
Rkis the kth power of the relation R. [8+8]
(b) Let R be a relation on the set N of positive integers defined by the equation
x2 + 2y = 100, find the domain of R, range of R and R -1.
3. (a) Let L a finite distributive lattice. Then prove that every element in L can be
written uniquely (except for order) as the join of irredundant join-irreducible
elements. [8+8]
(b) Prove the independent laws for the elements of a lattice.
4. (a) Prove that any two simple connected graphs with n vertices and all of degree
two are isomorphic [8+8]
(b) Suppose G1 and G2 are isomorphic prove that if G1 is connected then G2 is
also connected.
5. (a) Prove that the Kuratowskis second graph consisting of 6 vertices and 9 edges
is non-planar.
(b) State criteria to detect the planarity of a connected graph and give an example
also. [8+8]
6. (a) Describe the applications and efficiency level of breadth-first traversal.
(b) What is a minimum spanning tree? What are the different ways of creating
minimum spanning trees. [8+8]
7. (a) How many integral solutions are there to x1 + x2 + x3 + x4 + x5 = 20 where
each xi 2 ? [8]
(b) Find the number of district triples (x1, x2, x3) of nonnegative integers satisfying
the inequality x1 + x2 + x3 < 6. [8]
8. Solve the recurrence relation an-9an-1+26an-2 - 24an-3=0 for n 3. [16]

1 of 1

Return to question paper search

Next Question Paper: Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 1]

Previous Question Paper: Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 3]