## Graph Theory and Combinatorics - Dec 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)** Define graph isomorphism and isomorphic graphs. Determine whether the following graphs are isomorphic or not:

(5 marks)
**1 (b)** Define complement of a simple graph. 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 (c)** Let G=(V,E) be a connected undirected graph. What is the largest possible values for |V| if |E|=19 and deg(v)?4 for all v ∈ V?(4 marks)
**1 (d)** Write a note on "Konigsberg bridge problem and its solution".(6 marks)
**2 (a)** Define planar graph. Prove that the Peterson graph is nonplanar.(5 marks)
**2 (b)** Define Hamilton cycle. How many edge disjoint Hamilton cycle exist in the complete graph seven vertices? Also draw the graph to show these Hamilton cycle.(5 marks)
**2 (c)** Define dual of a planar graph. Construct the dual of the planar graph given below.

(4 marks)
**2 (d)** Define chromatic number and chromatic polynomial. Determine the chromatic polynomial for the graph shown below

(6 marks)
**3 (a)** A class room contains 10 micro computer that are to be connected to a wall socket that has 2 outlets. Connections are made by using extension cords that have 2 outlets each. Find the least number of cords needed to get these computer set up for use.(4 marks)
**3 (b)** Apply merge sort to the list -1, 0, 2, -2, 3, 6, -3, 5, 1, 4.(4 marks)
**3 (c)** Find all the spanning trees of the graph shown below. Also find all the non isomorphic spanning trees.

(6 marks)
**3 (d)** Obtain an optimal prefix code for the message MISSION SUCCESSFUL. Indicate the code for the message.(6 marks)
**4 (a)** State Kruskal's algorithm. Using Kruskal's algorithm find a minimal spanning tree for the weighted graph given below.

(8 marks)
**4 (b)** Apply Dijkstra's algorithm the diagram shown in Fig. Q4(b) and determine the shortest distance from vertex a to each of the other vertices in the directed graph.

(6 marks)
**4 (c)** Define the following with one example for each: i) cut set

ii) Edge connectivity

iii) Vertex connectivity.(6 marks)
**5 (a)** A bit is either 0 or 1. A byte is a sequence of 8 bits. Find: i) The number of bytes; ii) The number of bytes that begin with 11 and end 11; iii) the number of bytes that begin with 11 and do not end with 11 and iv) the number of bytes that begin 11 or end with 11.(6 marks)
**5 (b)** How many arrangement of the letters in MISSISSIPPI have no consecutive S's?(5 marks)
**5 (c)** Find the coefficient of x^{9} in the expansion of $$ 3\left ( x^2 - \dfrac {2}{x} \right )^{15} $$(5 marks)
**5 (d)** In how many ways can we distribute 7 apples and 6 oranges among 4 children so that each child gets at least 1 apple?(4 marks)
**6 (a)** How many integers between 1 and 300 (inclusive) are

i) Divisible by at least one of 5, 6, 8?

ii) Divisible by none of 5, 6, 8?(6 marks)
**6 (b)** Define derangement. Find the number of derangement of 1, 2, 3, 4. List all the derangements.(6 marks)
**6 (c)** Five teachers T_{1}, T_{2}, T_{3}, T_{4}, T_{5} are to be made class teachers for five classes C_{1}, C_{2}, C_{3}, C_{4}, C_{5} one teacher for each class T_{1} and T_{2} do not wish to become the class teachers for C_{1} or C_{2}, T_{3} and T_{4} for C_{4} or C_{5} and T_{5} for C_{3} or C_{4} or C_{5}. In how many ways can the teacher be assigned the work?(8 marks)
**7 (a)** Find the generating function for the sequence 8, 26, 54, 92, ......(6 marks)
**7 (b)** Using generating function, find the number of i) non negative and ii) positive integer solutions of the equation x_{1}+x_{2}+x_{3}+x_{4}=25.(8 marks)
**7 (c)** Define exponential generating functions using exponential generating function find the number of ways in which 5 of the letters in the word CALCULUS be arranged.(6 marks)
**8 (a)** The number of bacteria in culture is 1000 (approximately) and this number increase 250% every two hours. Use a recurrence relation to determine the number of bacteria present after one day.(5 marks)
**8 (b)** Solve the recurrence relation

a_{n+2}-4a_{n+1}=-200, n≥0 and a_{0}=3000, a_{1}=3300.(7 marks)
**8 (c)** Find the generating function for the recurrence relation a_{n+1}-a_{n}=n^{2}, n≥0 and a_{0}=1.(8 marks)