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 K_3,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 b₁, b₂, b₃, b₄ and girls g₁, g₂, g₃, g₄ are such that
b₁ is a cousin of g₁, g₂ and g₄
b₂ is cousin of g₂ and g₄
b₃ is a cousin of g₂ and g₃.
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) xyz² in the expansion of (2x-y-z)⁴
ii) a³b³c²d⁵ in the expansion of (a+2b-3c+2d+5)¹⁶(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 x¹⁸ 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 x₁+x2+x₃+x₄=25(6 marks) 7 (c) Find all the partitions of x⁷.(7 marks) 8 (a) Solve the Fibonacci relation.
F_n+2=F_n+1+F_n for n≥ 0 given F₀=0 and F₁=1.(7 marks) 8 (b) Solve the recurrence relation
a_n-2 a_n-1 + a_n-2 =5_n.(7 marks) 8 (c) Find a generating function for the recurrence relation
a_r+5a_r-1 +6a_r-2 = 3r², r≥2.(6 marks)