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

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

1. Show that the following posets are not lattices.

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

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

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.

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

4. Find a switching circuit for the logic expression

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

5. Implement

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

3. What is Konigsberg’s Bridge problem?

1. Test isomorphism for the following graphs and

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

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:

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: