Bengal Engineering and Science University 2006 B.E Computer Science and Engineering Discrete Structures - Question Paper
the ques. paper is with the attachment.
Ex/BESUS/ CST-401/06
B.E. (CST) Part-II 4th Semester Examination, 2006
Time : 3 hours Full Marks : 100
Use separate answerscript _for each half. Answer SIX questions, taking THREE _ from each half. Two marks are reserved_for neatness in each half.
FIRST HALF
1. a) State Handshaking lemma. Use it to prove that every planar graph has at least one vertex of degree < 5.
b) Prove that K33 is non-planar.
c) Every planar graph can be embedded on the surface of a plane in which some specified face in exterior - Justify this fact. (7+6+3)
2. a) Define outer planar graph. Prove that vertex connectivity of an outer planar graph is two. (Assume the graph is biconnected).
b) Edge connectivity of a planar graph is at most 5. Justify.
c) Define 1-isomorphism. Prove that rank of a graph is invariant under
1-isomorphism. (6+5+5)
3. a) Prove that every planar graph is 5-colorable.
b) Define chromatic polynomial of a graph. Derive chromatic polynomial of a tree of n vertices.
c) Derive a generating function for the numeric function (1, 2, 3, ...., r, ....).
(6+5+5)
4. a) Solve the following recurrence relation
4ar-20ar_i + 17ar_2 - 4ar_3 = 0.
b) Find particular solution of
ar- 2ar_! - 3.2r.
c) Use suitable generating function to solve the recurrence relation given below.
ar = 3 ar_, + 2 , r > 1 , a0 = 1. (6+4+6)
5. a) Define : Logical consequence.
b) Given : If it is Sunday and nice weather then we go swimming. Today is Sunday. Weather is nice.
Show that "we will go swimming" is logical consequence of the above text.
c) What is logical paradox? Give an example. (3+8+5)
6. Obtain the clause form of the following. (4x4)
i) All that glitters is not gold.
ii) Only one person spoke at the meeting.
iii) There is no business like showbusiness.
iv) 5 is a prime number and it is odd, therefore there exists an odd prime number.
7. a) Write down the converse of the following statement about integers :
Ifx andy are odd, thenx-A is even.
Is the statement you wrote down true or false?
Prove or disprove your answer.
b) Prove the following statements, where m and n are integers.
If x = 5m + 6 andy=5n + 6, then xy= 5k+6 for some integer k.
c) Prove the following statement about divisibility of integers
If d\a and d\b then d\(ax + by) for any integers x andy.
d) Prove the following iff statement about integers.
x is odd if and only if 81 (x2 - 1). (4x4)
8. a) What is Principle of Mathematical Induction?
b) Prove by principle of mathematical induction that the following function computes 2 + 4 + .... +2n for any natural number n :
f(n) = if n = 0 then 0 else f(n-l) + 2n
c) Use Induction to prove that each function performs the stated task,
i) The function g computes the number of nodes in a binary tree : g(D= if r = ()thenO
else 1 + g (left (T)) + g (right (7)).
ii) The function h computes the number of leaves in a binary tree : h(T)= ifr = (>thenO
else if T = tree ((>, x, < then 1
else h (left (T)) + h (right (T)). (1+5+10)
|
Attachment: |
| Earning: Approval pending. |
