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⁹ 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₁, T₂, T₃, T₄, T₅ are to be made class teachers for five classes C₁, C₂, C₃, C₄, C₅ one teacher for each class T₁ and T₂ do not wish to become the class teachers for C₁ or C₂, T₃ and T₄ for C₄ or C₅ and T₅ for C₃ or C₄ or C₅. 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₁+x₂+x₃+x₄=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₀=3000, a₁=3300.(7 marks) 8 (c) Find the generating function for the recurrence relation a_n+1-a_n=n², n≥0 and a₀=1.(8 marks)