Graph Theory and Combinatorics - Dec 2012
Computer Science Engg. (Semester 4)
TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Define a connected graph. Prove that a connected graph with n vertices has at least (n-1) edges.(6 marks) 1 (b) Define isomorphism of two graphs. Determine whether the two graphs (Fig Q1(b) (i)) and (Fig Q1(b) (ii))
(7 marks) 1 (c) Define a complete graph. In the complete graph with n vertices, where n is an odd number ≥3, show that there are (n-1)/2 edge disjoint Hamilton cycles.(7 marks) 2 (a) Design a regular graph with an example. Show that the Peterson graph is non planar graph.(7 marks) 2 (b) Prove that a graph is 2-chromatic if and only if it is a null bipartite graph.(6 marks) 2 (c) Define Hamilton and Eulerian graphs. Prove the complete graph K3,3 is Hamilton but not Eulerian.(7 marks) 3 (a) Define a tree. Prove that a connected graph is a tree if it is minimally connected.(6 marks) 3 (b) Define a spanning tree. Find all the spanning trees of the graph given below. (Fig Q3(b))
(7 marks) 3 (c) Construct a optimal prefix code for the symbols a, o, q, u, y, z that occur with frequencies 20, 28, 4, 17, 12, 7 respectively.(7 marks) 4 (a) Define matching edge connectivity and vertex connectivity. Give one example for each.(6 marks) 4 (b) Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown in the following Fig Q4(b).
(7 marks) 4 (c) Three boys b1, b2, b3, b4 and girls g1, g2, g3, g4 are such that
b1 is a cousin of g1, g2 and g4
b2 is cousin of g2 and g4
b3 is a cousin of g2 and g3.
If a boy must marry a cousin girl, find possible sets of such couples.(7 marks) 5 (a) Find the number of ways of giving 10 identical gift boxes to six person A, B, C, D, E, F in such a way that the total number of boxes given to A and B together does not exceed 4.(6 marks) 5 (b) Define Catalan number. In how many ways can one travel in the xy plane from (0, 0) to (3, 3) using the moves R:(x+1, y) and U:(x, y+1) if the taken may touch but never rise above the line y=x? Draw two such paths in the xy plane.(7 marks) 5 (c) Determine the coefficient of
i) xyz2 in the expansion of (2x-y-z)4
ii) a3b3c2d5 in the expansion of (a+2b-3c+2d+5)16(7 marks) 6 (a) How many integers between 1 and 300 (inclusive) are
i) divisible by 5, 6, 8?
ii) divisible by none of 5, 6, 8?(7 marks) 6 (b) In how many ways can the integers 1, 2, 3, ....., 10 be arranged in a line so that no even integer is in it natural place?(6 marks) 6 (c) Find the rook polynomial for the following board (Fig Q6(c)).
(7 marks) 7 (a) Find the coefficient of x18 in the following products: $$ i) \ (x+x^2+x^3+x^4+x^5)(x^2+x^3+x^4+x^5+\cdots \ \cdots)^5 \\ ii) (x+x^3+x^5+x^7+x^9)(x^3+2x^4+3x^5+ \cdots \ \cdots )^3 $$(7 marks) 7 (b) Using the generating function find the number of i) non negative and
ii) positive integer solutions of the equation x1+x2+x3+x4=25(6 marks) 7 (c) Find all the partitions of x7.(7 marks) 8 (a) Solve the Fibonacci relation.
Fn+2=Fn+1+Fn for n≥ 0 given F0=0 and F1=1.(7 marks) 8 (b) Solve the recurrence relation
an-2 an-1 + an-2 =5n.(7 marks) 8 (c) Find a generating function for the recurrence relation
ar+5ar-1 +6ar-2 = 3r2, r≥2.(6 marks)