Bhavnagar University 2007 B.Sc Computer Science DISCRETE MATHEMATICS - Question Paper

DiscRETE MATHEMATICS



Time: three hrs
Max Marks: 70

First ques. is Compulsory

ans any 4 from the remaining ques.

All ques. carry equal marks

ans all parts of any ques. at 1 place

1. ans the subsequent
a) Write the elements of the set P(P(P(f))) where P(A) denotes the power set of the set A and f denotes the empty set.
b) Write the subsequent statement in predicate calculus:
There is a brother for every person.
c) How many ways can 12 people have their birthdays in various calendar months?
d) obtain the number of divisors of 400.
e) Write the characteristic formula of Sk-7Sk-2+6Sk-3=0.
f) Write the adjacency matrix of the subsequent digraph.
-----DIAGRAM-----
g) Draw all possible binary trees with 3 nodes.

2. a) Check whether ((P? Q)? R)?((P? Q)?(P? R)) is a tautology.

b) Write the subsequent phrases into predicate logic statements and verify the conclusion.
All trees are graphs.
a few graphs are trees.
AND - OR graph is a graph.
MST is a tree.
Therefore, MST is a graph.

3. a) obtain the nuniber of integer solutions to the formula
x1 + x2 +x3 + x4 + x5 = 20 where x1 = 3, x2 = 2, x3 = 4. x4 = six and x5 = 0.

b) A simple code is made by permuting the letters of the alphabet of 26 letters with every letter being changed by a distinct letter. How many various codes can be made in this way?

4. a) obtain the number of ways of placing 20 similar balls into six numbered boxes so that the 1st box contains any number of balls ranging from one and five inclusive and the other five boxes must contain two or more balls every.

b) Solve an - 6an-1+12an-2 - 8an-3 - 0 by generating functions for n = 3.

5. a) obtain the transitive closure of the digraph whose adjacency matrix is

0 one 0 0 0
0 0 one 0 0
1 0 0 one 1
0 0 0 0 1
0 0 0 0 0b) Prove that a graph G is a tree if and only if G has no cycles and the number of the edges of G is 1 less than the number of vertices of G.

6. a) Write Kruskal’s algorithm for finding the minimum spanning tree of a graph

b) obtain the minimum spanning tree of the graph provided by the adjacency matrix

0 one 0 0 0
1 0 one 0 0
0 one 0 one 1
0 0 one 0 0
0 0 one 0 07. a) State and prove the Euler’s formula for planar graphs.

b) How many various Hamiltonian cycles are there in a complete graph of n vertices? Justify your ans.

8. a) What is graph coloring? State the four-color theorem.

b) Prove that every simple planar graph is 5-colorble.

Earning:   Approval pending.