## 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_{5} and K_{303} 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_{1}, B_{2}, B_{3} and four girls G_{1}, G_{2}, G_{3}, G_{4} are such that i) B_{1} is a cousin of G_{1}, G_{3}, G_{4} , ii) B_{2} is a cousin of G_{2} and G_{4} , iii) B_{3} is a cousin of G_{2} and G_{3}. 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^{9}y^{3} in the expansion of (2x - 3y)^{12}.

ii) a^{2}b^{3}d^{5} in the expansion of (a + 2b - 3c + 2d + 5)^{16}
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_{1}, B_{2}, B_{3}, B_{4}. The boys B_{1} and B_{2} do not wish to have apple, the boy B_{3} does not want banana or mango, and B_{4} 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_{1} + x_{2} + x_{3} + x_{4} = 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_{1} = 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