BA 6th Semester Question Papers: Discrete Mathematics and Graph Theory (May' 2015)

2015

(May)

MATHEMATICS

(Major)

Course: 602

(Discrete Mathematics and Graph Theory)

Full Marks: 80

Pass Marks: 32

Time: 3 hours

The figures in the margin indicate full marks for the questions.

(A) DISCRETE MATHEMATICS

(Marks: 45)

1. Answer the following questions: 1x5=5

1. The roots of the characteristic equation of a recurrence relation are Find its general solution.
2. It a lattice, if then is it true?
3. Give an example of an infinite lattice without and.
4. Prove that in a complemented lattice
5. A lattice L is given as

   a

  

1 Is it a Boolean algebra?

2. Answer the following questions: 2x3=6

1. Show that the following posets are not lattices.

Where is being defined as if divides.

2. Show that the Lattice, as given below is complemented.

       1

  

   

0      

3. Find 5 (five sub lattices ofhaving 5 (five) elements.

3. Answer any two of the following questions: 3x2=6

1. Solve the recurrence relation
2. Show that every subset of a chain is a lattice.
3. For being a Boolean algebra. Prove that iff.

4. Answer any two of the following questions: 5x2=10

1. Define lattice homomorphism. Show that the given two latticesand are isomorphic. Hereis the power set of with order relation and is the set of divisors of 30 with order relation (divisors).
2. Define minterm and maxterm with examples. Obtain the sum-of-product canonical form for the Boolean expression
3. Represent the Boolean function

By its Karnaugh map and minimize.

Or

4. Find a switching circuit for the logic expression

5. Answer any three of the following questions: 6x3=18

1. Find the solution of the recurrence relation
2. Define generating function of a sequence. If is the matrix, evaluate using recurrence relation and hence find.
3. Show that the minterms of the variables have the properties

1. for
2. 

4. Find the minimal form of the Boolean expression

by binary valuation process.

5. Implement

with multiplexer.

(B) GRAPH THEORY

(Marks: 35)

6. Answer the following questions: 1x3=3

1. Give an example of pseudo graph.
2. For the graph given below, draw the sub graph

h

G= b g

f d

c

3. What is Konigsberg’s Bridge problem?

7. Answer the following questions: 2x2=4

1. Test isomorphism for the following graphs and

2. Show that the graph as shown below contains no Eulerian circuit:

8. Answer any two of the following questions: 5x2=10

1. Prove that a simple graph with vertices and components can have at most edges.
2. State and prove handshaking theorem.
3. Find the sum of the graphs and as given below:

   

: :

               

       

9. Answer any three of the following questions: 6x3=18

1. What is the difference between Eulerian and Hamiltonian graphs? For a single connected graph with vertices, if deg + deg, for each vertices and not connected by an edge, then prove that is Hamiltonian.

2. Obtain simple graph, pseudo graph and multi graph from the following graph:

3. Define adjacency matrix with example. Draw the graph represented by the following adjacency matrix:

4. Prove that in a complete graph with vertices, there are edges disjoint Hamiltonian circuits, if is an odd number.

5. What do you mean by linked representation of a graph? Draw adjacency structure for the graph given below: