Graph Theory and its Applications - May 2016

VTU Computer Science (Semester 4)

Total marks: --
Total time: -- INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary 1(a) Define : i) Complete Bipartite Graph ii) Regular Graph and iii) Induced Subgraph. Give one example for each. 6 marks

1(b) For a graph with n vertices and m edges, if δ is minimum and Δ is maximum of the degrees of vertices show that δ ≤ (2m/n) ≤ Δ. 6 marks

1(c) Show that the following graph is isomorphic to Kuratowski's second Graph (K_3.3)
6 marks

1(d) Write a note on Konigsberg's seven Bridge problems. 6 marks

2(a) Prove that a connected planer graph G with n vertices and m edges has exactly (m - n + 2) regions in everyone one of its diagrams. 6 marks

2(b) State and explain Kuratowski's theorem. Show that the graphs K₅ and K₃₀₃ are non-planer by re-drawing them. 6 marks

2(c) Find the chromatic polynomial for the following graph. If 5 colors are available, in how many ways can the vertices of this graph be properly colored?
6 marks

3(a) Define Trees, Prove that a tree with n-vertices has n-1 edges. 6 marks

3(b) Define: i) Spanning Tree ii) Rooted Tree and iii) Full Binary Tree. Give on example for each. 6 marks

3(c) Explain prefix codes. Obtain an optimal prefix code for the message MISSION SUCCESSFUL. Indicate the code for the message. 6 marks

4(a) Explain the steps in Dijkstra's shortest path algorithm. 6 marks

4(b) Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown below.
6 marks

4(c) Three boys B₁, B₂, B₃ and four girls G₁, G₂, G₃, G₄ are such that i) B₁ is a cousin of G₁, G₃, G₄ , ii) B₂ is a cousin of G₂ and G₄ , iii) B₃ is a cousin of G₂ and G₃. If boys must marry a cousin girl, find the possible sets of such couples. 6 marks

5(a)(i) How many arrangements are there for all letters in the word SOCIOLOGICAL? 6 marks

5(a)(ii) In how many of these arrangements

5(b) Find the co-efficient of
i) x⁹y³ in the expansion of (2x - 3y)¹².
ii) a²b³d⁵ in the expansion of (a + 2b - 3c + 2d + 5)¹⁶ 6 marks

5(c) In how many ways can one distribute eight identical balls into four distinct containers so that i) no container is left empty? ii) the fourth container gets an odd number of balls? 6 marks

6(a) State and prove the principle of Inclusion - Exclusion for n sets. 6 marks

6(b) In how many ways can the 26 letters of the English alphabet be permuted so that none of the patterns CAR, DOG, PIN, and BYTE occurs? 6 marks

6(c) In how many ways can be integers 1, 2, 3, ..... 10 be arranged in a line so that no even integer is in its natural place? 6 marks

6(d) An apple, a banana, a mango, and an orange are to be distributed to four boys B₁, B₂, B₃, B₄. The boys B₁ and B₂ do not wish to have apple, the boy B₃ does not want banana or mango, and B₄ refluses orange. In how many ways the distribution can be made so that no boy is displeased? 6 marks

7(a) Using the generating functions, find the number of i) non negative, and ii) positive, integer solutions of the equation x₁ + x₂ + x₃ + x₄ = 25. 6 marks

7(b) A bag contains a large number of red, green, white and black marbles, with atleast 24 of each colour. In how many ways can one select 24 og these marbles, so that there are even number of white marbles and atleast six black marbles. 6 marks

7(c) Using exponential generating function, find the number of ways in which four of the letters in the word ENGINE be arranged 6 marks

8(a) Solve the recurrence relation.
a_n = 2a_h/2 + (n-1) for n = 2^k, k ≥ 1, given a₁ = 0. 6 marks

8(b) The number of virus affected files in a system is 1000 (to start with) and this increase 250% every two hours. Using a recurrence relation determine the number of virus affected files in the system after one day. 6 marks

8(c) Find and solve a recurrence relation for the number of binary sequences of length n ≥ 1 that have no consecutive O's. 6 marks