Graph Theory and Combinatorics - Dec 2013

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) Prove that in every graph, the number of vertices of odd degree is even.(5 marks) 1 (b) Show that a simple graph of order n=4 and size m=7 and a complete graph of order n=4 and size m=5 do not exist.(4 marks) 1 (c) Define isomorphism of two graphs. Show that the two graphs given below are isomorphic.
(5 marks) 1 (d) Discuss Konigsberg bridge problem and the solution of the problem.(6 marks) 2 (a) Show that Kuratoski's first graph, K₅ is non-planar.(5 marks) 2 (b) Show that in a complete graph with 'n' vertices where n is an odd number and n≥3, there are $$ \dfrac {n-1}{2} $$ edge disjoint Hamilton cycles.(5 marks) 2 (c) Define dual of a planar graph. Draw the geometric dual of the given graph.
(5 marks) 2 (d) Define chromatic number. Find O(G, λ) for the Fig. Q2(d).
(5 marks) 3 (a) Define a tree. Prove that the tree with P vertices has P-1 edges(6 marks) 3 (b) Find all spanning trees of the graph shown below:
(6 marks) 3 (c) Construct an optimal prefix code for the symbols A, B, C, D, E, F, G, H, I, J that occur with respective frequencies 78, 16, 30, 35, 125, 31, 20, 50, 80, 3.(6 marks) 3 (d) If a tree T has four vertices of degree 2. one vertex of degree 3, two vertices of degree 4 and one vertex of degree 5, find the number of leaves in T.(4 marks) 4 (a) Define i) cut set, ii) edge connectivity, ii) bridge connectivity, iv) matching with examples.(4 marks) 4 (b) Apply Dijkstra's algorithm to the following weighted graph shown in below Fig Q4(b) and determine the shortest distance from vertex 'a' to each of the other six vertices in the graph.
(6 marks) 4 (c) Using Kruskal's algorithm, find a minimal spanning tree for the weighted graphs shown in Fig. Q4(c).
(5 marks) 4 (d) For the network shown in Fig. Q4(d). Find the capacities of all the cut-set between the vertices a and d and hence determine the maximum flow between a and b.
(5 marks) 5 (a) A woman has 11 close relatives and she wishes to invite 5 of them to diner. In how many ways can she invite them in the following situations:
i) There are no restrictions on the choice
ii) Two particular persons will not attend separately
iii) Two particular persons will not attend together.(6 marks) 5 (b) Find the coefficient of x¹¹ y⁴ z² in the expansion of (2x³-3xy²+z²)⁶.(7 marks) 5 (c) Define Catalan numbers. Using the moves: R(x,y)→(x+1, y) and U(x,y)→(x, y+1) find in how many ways can one go from: i) (0,0) to (6,6) and not rise above the line y=x ii) (2,1) to (7,6) and not rise above the line y=x-1.(7 marks) 6 (a) In how many ways can the 26 letters of the English alphabet be permitted so that none of the patterns CAR, DOG, PUN or BYTE occurs?(7 marks) 6 (b) For the positive integers 1, 2, 3, ......., n there are 11660 derangement where 1, 2, 3, 4, 5 appear in the first five positions. What is the value of n?(6 marks) 6 (c) Four person P₁, P₂, P₃, P₄ who arrive late for a dinner party find that only one chair at each of five tables T₁, T₂, T₃, T₄ and T₅ in vacant. P₁ will not sit at T₁ or T₂. P₂ will not sit at T₂, P₃ will not sit at T₃ or T₄ and P₄ will not sit at T₄ or T₅. Find the number of ways they can occupy the vacant chairs.(7 marks) 7 (a) Find the generating function for the sequence 0, 2, 6, 12, 20, 30, 42, .......(7 marks) 7 (b) In how many ways can 12 oranges be distributed among three children A, B, C so that A gets at least four B and C get out least two, but C gets no more than five?(6 marks) 7 (c) Define exponential generating functions. Find the exponential generating function for the number of ways to arrange n letter selected from MISSISSIPPI.(7 marks) 8 (a) Find the recurrence relation and the initial condition for the sequence 2, 10, 50, 250, ...... Hence find the general term of the sequence.(6 marks) 8 (b) Solve the recurrence relation a_n+a_n-1-6a_n+2=0 for n?2 given that a₀=-1 and a₁=8(7 marks) 8 (c) Using the generating function solve the recurrence relation a_n-3a_n-1=n, n≥1 given a₀=1(7 marks)