Graph Theory and Combinatorics : Question Paper Jun 2014 - Computer Science Engg. (Semester 4) | Visveswaraya Technological University (VTU)

16views

written 8.1 years ago by

Graph Theory and Combinatorics - Jun 2014

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) Let G be a simple graph of order n. If the size of G is 56 and the size of G is 80. What is n?(5 marks) 1 (b) Define isomorphism of graphs. Show that the following two graphs in Fig. Q1(b) are isomorphism.
(5 marks) 1 (c) Define connected graph. Give an example of connected graph G, where removing any edge e results in an disconnected graph.(5 marks) 1 (d) Discuss Konigsberg bridge problem.(5 marks) 2 (a)

Define Hamilton cycle. If G=(V, E) is a loop free undirected graph with |V|=n≥3 and if $|E| \geq \begin{bmatrix} n-1\\\\ 2 \end{bmatrix}$ then prove that G has Hamilton cycle.

(6 marks) 2 (b) Define planar graph. If a connected planar graph G has a n vertices e edges and r regions then prove that n-e+r=2.(7 marks) 2 (c) Define chromatic number. Find the chromatic polynomial for the cycle of length 4. Hence find its chromatic number?(7 marks) 3 (a) Define a tree. Prove that in a tree T=(V, E), |V|=|E|+1(6 marks) 3 (b) Define: i) prefix code ii) balanced tree, Give one example for each. Find all the spanning trees of the graphs as shown in Fig Q3(b).

(7 marks) 3 (c) Construct an optimal prefix code for the letters of the word ENGINEERING. Hence deduce the code for this word.(7 marks) 4 (a) Define: i) Edge-connectivity ii) Vertex-connectivity and iii) Complete matching. Give an example for each.(6 marks) 4 (b) State Kruskal's algorithm. Apply Kruskal's algorithm to find a minimal spanning tree for the following weighted graph as shown in Fig. Q4(b)

(7 marks) 4 (c) State Max-flow and Min-cut theorem. For the network shown below in Fig. Q4(c), find the capacities of all the cut sets between the vertices A ,D and hence the maximum flow.

(7 marks) 5 (a) How many arrangement are there for all letters in the word SOCIOLOGICAL? In how many of these arrangements: i) A and G are adjacent ii) all the vowels are adjacent.(5 marks) 5 (b) In how many ways can one distribute eight identical balls into four distinct containers so that,
i) no containers is left empty, ii) the fourth container gets an odd number of balls.(5 marks) 5 (c) Determine the coefficient of x² y² z³ in the expansion of (3x-2y-4z)⁷(5 marks) 5 (d) Using the moves R:(x,y)→(x+1, y) and U:(x,y)→(x, y+1) find in how many ways can one go,
i) From (0, 0) to (6, 6) and not rise above the line y=x.
From (2, 1) to (7, 6) and not rise above the line y=x-1
iii) From (3, 8) to (10, 15) and not rise above the line y=x+5.(5 marks) 6 (a) Determine the number of positive integers n such that 1≤ n ≤ 10 and n is not divisible by 2, 3 or 5.(6 marks) 6 (b) Define derangement. There are eight letters to eight different people to be placed in eight different addressed envelopes. Find the number of ways of doing this so that at least one letter gets to the right person.(7 marks) 6 (c) Find the rook polynomial for the 3×3 board using the expansion formula.(7 marks) 7 (a) Find the generating functions for the following sequences:
i) 0², 1², 22, 3² , ......
ii) 0, 2, 6, 12, 20, 30, 42, ........(6 marks) 7 (b) Find the number of ways of forming a committee of 9 students drawn from 3 different classes so that students from the same class do not have an absolute majority in the committee.(7 marks) 7 (c) Using exponential generating function, find the number of ways in which four of the letters in the word ENGINE be arranged.(7 marks) 8 (a) The number of virus affected files in a system is 1000 (to star with) and this number increase 250% every two hours. Use a recurrence relation to determine the number of virus affected files in the system after one day.(6 marks) 8 (b) Solve the recurrence relation:
a_n2 + 3a_n-1+2a_n =3ⁿ, n≥0 give a₀=0, a₁=1(7 marks) 8 (c) Find the generating function for the recurrence relation C_n = 3C_n-1-2C_n-2 for n≥2. Given C₁=5, C₂=3. Hence solve it.(7 marks)

ADD COMMENT EDIT