Graph Theory and its Applications - December 2015

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) Determine the order |V| of the graph G=(V,E) in the following cases:
i) G is a cubic graph with 9 edges
ii) G is regular with 15 edges
iii) G has 10 edges with 2 vertices of degree 4 and all other vertices of degree 3. 7 marks

1 (b) Define isomorphism of any two graphs. Show that the following graphs are not isomorphic.
7 marks

1 (c) Prove that: Any connected graph G is Euler if and only if all the vertices of G are of even degree. 7 marks

2 (a) i) Planar graph
ii) Non-planar graph
Show that the complete graph K_s is a non-planar graph. 7 marks

2 (b) Write down the step involved in the detection of planarity by method of elementary reduction. 7 marks

2 (c) Determine chromatic number and chromatic polynomial for the graph given below:
7 marks

3 (a) Prove that A connected graph is a tree if and only if it is minimally connected. 7 marks

3 (b) Find all the spanning tress of the graph shown below:
7 marks

3 (c) Obtain the optimal prefix code for the word VISVESVARAYA. Indicate the code. 7 marks

4 (a) Determine the shortest path from the vertex 'a' to every other vertices in the following directed graph (Fig. Q4(a)).
7 marks

4 (b) Using the Kruskal's algorithm, find a minimal spanning tree of the weighted graph shown in Fig. Q4(b).
7 marks

4 (c) For the network shown in Fig, Q4(c), determine the maximum flow between the vertices A and D by identifying the cut-set of minimum capacity.
7 marks

5 (a) A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many ways can she invite them in the following situations?
i) Two particular persons will not attend separately
ii) Two particular persons will not attend together. 7 marks

5 (b) Determine the coefficient of:
i) xyz² in the expansion of (2x-y-z)⁴.
ii) x²y²z² in the expansion of (3x-2y-4z)⁷. 7 marks

5 (c) 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.
ii) From (2,1) to (7,6) and not rise above the line y=x-1.
iii) From (3,3) to (10,15) and not rise above the line y=x+5. 7 marks

6 (a) Determine the number of positive integers n such that 1≤n≤100 and n is not divisible by 2, 3, or 5. 7 marks

6 (b) There are n pairs of Children's gloves in a box. Each pair is of a different colour. Suppose the right gloves are distributed at random to 'n' children and thereafter the left gloves are also distributed to them at random. Find the probability that:
i) no child gets a matching pair
ii) every child gets a matching pair.
iii) exactly one child gets a matching pair and
iv) atleast 2 children get matching pairs. 7 marks

6 (c) Find the rook polynomial for the 3×3 board y using the expansion formula. 7 marks

7 (a) Find the generating function for the following sequence:
i) 1², 2², 3², 4², .....
ii) 0², 1², 2², 3², 4², .....
iii) 1³, 2³, 3³, 4³, ......
iv) 0³, 1³, 2³, 4³, ..... 7 marks

7 (b) In how many ways can we distribute 24 pencils to 4 children so that each child gets atleast 3 pencils but not more than 8. 7 marks

7 (c) Using generating function, find the number of partitions of n=6. 7 marks

8 (a) A bank pays a certain % of annual interests on deposits, compounding the interests once in 3 months. If a deposite doubles in 6 years and 6 months, what is the annual % of interest paid by the bank? 7 marks

8 (b) Solve the recurrence relation a_n+2-6a_n+1+9a_n=3×2ⁿ+7×3ⁿ for n≥0, given a₀=1, a₁=4. 7 marks

8 (c) Solve the recurrence relation a_n+1-a_n=3ⁿ, n≥0 with a₀=1 by using method of generating function. 7 marks