Question Paper: Graph Theory and Combinatorics : Question Paper Jun 2015 - Computer Science Engg. (Semester 4) | Visveswaraya Technological University (VTU)
0

Graph Theory and Combinatorics - Jun 2015

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) For the following graph determine,
i) A walk from b to d that is not trail
ii) A b-d trail that is not path
iii) A path from b to d
iv) A closed walk from b to b that is not a circuit
v) A circuit from b to b that is not a cycle
vi) A cycle from b to b
(6 marks)
1 (b) Define subgraph, spanning subgraph , induced subgraph and complete graph with example(7 marks) 1 (c) Prove that the undirected graph G=(V,E) has an Euler circuit if and only if G is connected and every vertex in G has even degree(7 marks) 2 (a) Define planar graph and prove that the following Petersen graph is nonplanar using Kuratowski's theorem (6 marks) 2 (b) Prove that in a complete graph with n-vertices, where n is an add number ≥ 3, there are (n-1)/2 edge-disjoint Hamiltonian cycles(7 marks) 2 (c) Find the chromatic polynomial for the following graph (7 marks) 3 (a) Prove that in every tree T=(V,E)$$\left | V \right |=\left | E \right |+1$$(6 marks) 3 (b) If T1=(V1,E1) and T2=(V2,E2) be two trees where $$\left | E_{1} \right |=17$$ and $$\left | V_{2} \right |=2\left | V_{1} \right |$$, then find $$\left | V_{1} \right |,\left [ V_{2} \right ] and \left | E_{1} \right |$$
ii) Let F2=(V2,E2) is a forest with $$\left | V_{2} \right |=62 and \left | E_{2} \right |=51$$ , how many trees determine F2
iii) Let F1=(V1,E) be a forest of 7 trees where $$\left | E_{1} \right |=40$$ what is $$\left | V_{1} \right |?$$
(7 marks)
3 (c) Construct an optional prefix code for the symbols a,o,q,u,y,z that occur with frequencies 20,28,4,17,12,7 respectively(7 marks) 4 (a) Using the Kruskal's algorithm, find a minimal spanning three of the following weighted graphs (8 marks) 4 (b) Using the Dijkstra's algorithm obtain the shortest path from vertex 1 to each of the other vertices in the following graph (7 marks) 4 (c) Prove that in bipartite graph G(V1,V2,E) if there is positive integer M such that the degree of every vertex in V1≥M≥ the degree of every vertex in V2 then there exists a complete matching from V1 to V 2(7 marks) 5 (a) i) How many arrangements all there for all letters in the word SOCIOLOGICAL?
ii) In how many of these arrangements, A and G are adjacent?
iii) In how many of these arrangements, all the vowels are adjacent>
(6 marks)
5 (b) Determine to co-efficient of :
i) x9y3 in the expansion of (2x-3y)12
ii) x-y-z2 in the expansion of (2x-y-z)4
iii) x2-y2-z3 in the expansion of (3x-2y-4z)7
(7 marks)
5 (c) Determine the number of integer solutions for :x1+x2+x3+x4+x5<40,
where:
i) xi≥0, 1≤i≤5
ii)xi≥-3,1≤i≤5
(7 marks)
6 (a) Find the number of integers between 1 to 10,000 inclusive, which are divisible by none of 5,6 or 8(6 marks) 6 (b) Determine in how many ways can the letter in the word ARRANGEMENT be arranged so that there are exactly two pairs of consecutive identical letters(7 marks) 6 (c) i) Find the rook polynomial for the shaded chessboard

ii) Let A={1,2,3,4} and B={u,v,w,x,y,z}. How many one to one functions f:A → B satisfy none of the following conditions:
C1:f(1)=u or v; C2:f(2)=w; C3:f(3)=W or x; C4 : f(4)=x,y or z (7 marks) 7 (a) Find the coefficient of x15in $$\dfrac{(1+x)^{4}}{(1-x)^{4}}$$(6 marks) 7 (b) A ship carries 48 flags, 12 each of the colours red, white, blue and black. Twelve of these flags are placed on an vertical pole in order to communicate a signal to other ships. Determine, how many of these signals have at least three white flags or no white flags at all(7 marks) 7 (c) Find the formula to express : 02+12+22+--------+n2 as a function of n using summation on operator(7 marks) 8 (a) Solve the recurrence relation Fn+2=Fn+1+Fn where n ≥ 0 and F0=0 and F1=1(6 marks) 8 (b) i) A bank pay 6%interest compounded quarterly. If Laura inverts \$ 100 then how many months must she wait for her money to double?
ii) The number of bacteria in culture is 1000 and this number increase 250% every 2 hours. Use a recurrence relation to determine the number to bacteria present after one day.
(7 marks)
8 (c) Solve the recurrence relation :an+2-5a<sub<n+1&lt; sub="">+6an=2, n≥0, a0=3, a1=7 using method of generating functions</sub<n+1&lt;&gt;<>(7 marks)