## 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^{2} in the expansion of (2x-y-z)^{4}.

ii) x^{2}y^{2}z^{2} in the expansion of (3x-2y-4z)^{7}.
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}, 2^{2}, 3^{2}, 4^{2}, .....

ii) 0^{2}, 1^{2}, 2^{2}, 3^{2}, 4^{2}, .....

iii) 1^{3}, 2^{3}, 3^{3}, 4^{3}, ......

iv) 0^{3}, 1^{3}, 2^{3}, 4^{3}, .....
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^{n}+7×3^{n} for n≥0, given a_{0}=1, a_{1}=4.
7 marks

**8 (c)** Solve the recurrence relation a_{n+1}-a_{n}=3^{n}, n≥0 with a_{0}=1 by using method of generating function.
7 marks