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 T₁=(V₁,E₁) and T₂=(V₂,E₂) 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 F₂=(V₂,E₂) is a forest with $$\left | V_{2} \right |=62 and \left | E_{2} \right |=51$$ , how many trees determine F₂
iii) Let F₁=(V₁,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(V₁,V₂,E) if there is positive integer M such that the degree of every vertex in V₁≥M≥ the degree of every vertex in V₂ then there exists a complete matching from V₁ to V ₂(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) x⁹y³ in the expansion of (2x-3y)¹²
ii) x-y-z² in the expansion of (2x-y-z)⁴
iii) x²-y²-z³ in the expansion of (3x-2y-4z)⁷(7 marks) 5 (c) Determine the number of integer solutions for :x₁+x₂+x₃+x₄+x₅<40,
where:
i) x_i≥0, 1≤i≤5
ii)x_i≥-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