Graph Theory and Combinatorics - Jun 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 and give an example for each of the following: -
i) Connected graph
ii) Spanning subgraph
ii) Complement of a graph(6 marks) 1 (b) Define isomorphism. Show that the following graphs are isomorphism. (7 marks) 1 (c) In the graph given below find the number of paths from V₁ V₂. How many of these paths have length 5. (7 marks) 2 (a) Define Hamilton cycle. How many edge-disjoint Hamilton cycles exist in the complete graph with seven vertices? Also draw the graph to show these Hamilton cycles.(7 marks) 2 (b) Prove that Peterson graph is non-planar.(6 marks) 2 (c) Define chromatic number of a graph. Find the chromatic polynomial for the graph shown below and also find the chromatic number for the same. (7 marks) 3 (a) Define and give an example for each of the following:
i) Rooted tree
ii) Complete binary tree
iii) Balanced tree(6 marks) 3 (b) Construct an optimal prefix code for the symbols a, o, q, u, y, z that occur with the frequencies 20, 28, 4, 17, 12, 7 respectively.(7 marks) 3 (c) Obtain the optimal prefix code for the message "ROAD IS GOOD". Indicate the code.(7 marks) 4 (a) For the network shown below, determine the maximum flow between the vertices A and D by identifying the cutset of minimum capacity. (7 marks) 4 (b) State and prove max-flow and min-cut theorem.(6 marks) 4 (c) Apply PRIMS algorithm to determine a minimal spanning tree for the weighted graph shown below.

(7 marks) 5 (a) State and explain product rule of counting along with an example.(4 marks) 5 (b) Find the co-efficient of:
i) x⁹y³ in the expansion of (2x-3y)¹²
ii) x⁹ in the expansion (3x² - 2/x)¹⁵.(8 marks) 5 (c) i) From seven consonants and five vowels how many sets consisting of four different consonants and three different vowels can be formed.
ii) Find the number of arrangement of the letters in TALLAHASSEE which have no adjacent A's.(8 marks) 6 (a) Out of 30 students in hostel, 15 study history, 8 study economics and 6 study geography. It is know that 3 students all these subjects. Show that 7 or more students study none of these subjects,(6 marks) 6 (b) Find the number of derangements pf the integers from 1 to 2n satisfying the condition that the elements in the first n-places are:
i) 1, 2, 3, ......, n in some order
ii) n+1, n+2, ........., 2n in some order.(6 marks) 6 (c) What is the expansion formula for rook-polynomials? Find the rook polynomial for the 3×3 board by using the expansion formula.(8 marks) 7 (a) i) Find a generating function for the following sequence, 0², 1², 22, 3² .......
ii) Find the co-efficient of x²⁷ in the expansion of the following functions.
(x⁴+2x⁵+3x⁶+......)⁵.(6 marks) 7 (b) Using generating function, find the number of partitions of n=6.(7 marks) 7 (c) Define an exponential generating function. Find the exponential function for the number of ways to arrange n-letter n≥0, selected for each of the following words.
i) HAWAII
ii) MISSISSIPPI
iii) ISOMORPHISM(7 marks) 8 (a) Solve the recurrence relation (Fibonacci relation).
F_n+2=F_n+1+F_n given F₀=0 and F₁=1 and n≥0(6 marks) 8 (b) Solve the recurrence relation
a _n+3 -3a_n+2 + 3a_n+1 - a_n=3 +5n for n≥0(7 marks) 8 (c) Find a generating function for the recurrence relation
a_n+2-3a_n+1+2a_n=0, n≥0 and a₀=1, a₁=6. Hence solve it.(7 marks)