Graph Theory and Combinatorics - Jun 2013

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) i) Define a connected graph. Give an example of a connected graph G where removing any edge of G results in a disconnected graphs.
ii) Define complement of a graph. Find an example of a self-complementary graph on four vertices and one on five vertices.(6 marks) 1 (b) Find all (loop-free) non-isomorphic undirected graphs with four vertices. How many of these graphs are connected?(5 marks) 1 (c) Show that the following graphs in Fig Q1(c) are isomorphic:
(5 marks) 1 (d) How many different paths of length 2 are there in the undirected graph G in Fig. Q1(d)?
(4 marks) 2 (a) Define Hamilton cycle. How many edge-disjoint Hamilton cycles exist in the complete graph with seven vertices? Also draw the graph to show these Hamilton cycles.(6 marks) 2 (b) Define Planar graph. Let G=(V, E) be a connected planar graph or multigraph with |V|=V and |E|=e. Let r be the number of region in the plane determined by a planar embedding 0+G. Then prove that v-e+r=2.(7 marks) 2 (c) i) Find the chromatic number of the complete bipartite graph K_m,n and a cycle, C_n on n vertices n≥3.
ii) Determine the chromatic polynomial for the graph G in Fig. Q2(c).
(7 marks) 3 (a) i) Prove that in every tree T=(V,E), |E|=|V|-1.
ii) Let F₁=(V₁, E₁) be a forest of seven trees, where |E₁|=40. What is |V₁|?(7 marks) 3 (b) Define: i) Spanning tree ii) Binary rooted tree. Find all the non-isomorphic spanning trees of the graph Fig. Q3(b).
(6 marks) 3 (c) Define prefix code. Obtain an optimal prefix code for the message ROAD IS GOOD. Indicate the code.(7 marks) 4 (a) Apply Dijkstra's algorithm to the digraph shown in Fig. Q4(a) and determine the shortest distance from vertex a to each of the other vertices in the graph.
(7 marks) 4 (b) Define the following with respect to graph: i) matching ii) a cut-set. Show that the graph in Fig. Q4(b) has a complete matching from V₁ to V₂. Obtain two complete matching.
(7 marks) 4 (c) For the network shown below, find the capacities of all the cutsets between A and D, and hence determine the maximum flow between A and D.
(6 marks) 5 (a) How many arrangement of the letters in MISSISSIPPI have to consecutive S's?(5 marks) 5 (b) i) Find the coefficient of v²w⁴xz in the expansion of (3v+2w+x+y+z)⁸
ii) How many distinct terms arise in the expansion in part (i)?(5 marks) 5 (c) How many positive integers n can we form using the digits 3,4,5,5,6,7 if we want n to exceed 5000000?(5 marks) 5 (d) A message is made up of 12 different symbols and is to be transmitted through a communication channel. In addition to the 12 symbols, the transmitter will also send a total of 45 blank spaces between the symbols, with at least three spaces between each pair of consecutive symbols. In how many ways the transmitter sends such message?(5 marks) 6 (a) In how many ways can the 26 letters of the alphabet be permuted so that none of the patterns spin, game, path or net occurs?(7 marks) 6 (b) Define derangement. In how many ways can each of 10 people select a left glove and a right glove out of a total of 10 pairs of gloves so that no person selects a matching pair of gloves?(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?(7 marks) 7 (a) Find the generating function for the following sequences:
i) 1², 2², 3², 42, ......
ii) 0², 1², 2², 3², ......
ii) 0, 2, 6 12, 30, .....(6 marks) 7 (b) Use generating function to determine how many four element subset of S={1, 2, 3, ....., 15} contain to consecutive integers?(7 marks) 7 (c) Using exponential generating function, find the number of ways in which 4 of the letters in the words given below be arranged: i) ENGINE
ii) HAWAII(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.(5 marks) 8 (b) Solve the recurrence relation:
a_n+2-10a_n+1+21a_n=3n²-2, n?0(7 marks) 8 (c) Using the generating function method, solve the recurrence relation,
a_n-3a_n-1=n, n≥1 given a₀=1(8 marks)