STUPIDSID
1(a)
Define : i) Complete Bipartite Graph ii) Regular Graph and iii) Induced Subgraph. Give one example for each.
6 M
1(b)
For a graph with n vertices and m edges, if δ is minimum and Δ is maximum of the degrees of vertices show that δ ≤ (2m/n) ≤ Δ.
5 M
1(c)
Show that the following graph is isomorphic to Kuratowski's second Graph (K3.3)
5 M
1(d)
Write a note on Konigsberg's seven Bridge problems.
4 M
2(a)
Prove that a connected planer graph G with n vertices and m edges has exactly (m - n + 2) regions in everyone one of its diagrams.
7 M
2(b)
State and explain Kuratowski's theorem. Show that the graphs K5 and K303 are non-planer by re-drawing them.
6 M
2(c)
Find the chromatic polynomial for the following graph. If 5 colors are available, in how many ways can the vertices of this graph be properly colored?
7 M
3(a)
Define Trees, Prove that a tree with n-vertices has n-1 edges.
6 M
3(b)
Define: i) Spanning Tree ii) Rooted Tree and iii) Full Binary Tree. Give on example for each.
6 M
3(c)
Explain prefix codes. Obtain an optimal prefix code for the message MISSION SUCCESSFUL. Indicate the code for the message.
8 M
4(a)
Explain the steps in Dijkstra's shortest path algorithm.
6 M
4(b)
Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown below.
7 M
4(c)
Three boys B1, B2, B3 and four girls G1, G2, G3, G4 are such that i) B1 is a cousin of G1, G3, G4 , ii) B2 is a cousin of G2 and G4 , iii) B3 is a cousin of G2 and G3. If boys must marry a cousin girl, find the possible sets of such couples.
7 M
5(a)(i)
How many arrangements are there for all letters in the word SOCIOLOGICAL?
3 M
5(a)(ii)
In how many of these arrangements
A and G are adjacent All the vowels are adjacent
3 M
5(b)
Find the co-efficient of
i) x9y3 in the expansion of (2x - 3y)12.
ii) a2b3d5 in the expansion of (a + 2b - 3c + 2d + 5)16
i) x9y3 in the expansion of (2x - 3y)12.
ii) a2b3d5 in the expansion of (a + 2b - 3c + 2d + 5)16
6 M
5(c)
In how many ways can one distribute eight identical balls into four distinct containers so that i) no container is left empty? ii) the fourth container gets an odd number of balls?
8 M
6(a)
State and prove the principle of Inclusion - Exclusion for n sets.
5 M
6(b)
In how many ways can the 26 letters of the English alphabet be permuted so that none of the patterns CAR, DOG, PIN, and BYTE occurs?
5 M
6(c)
In how many ways can be integers 1, 2, 3, ..... 10 be arranged in a line so that no even integer is in its natural place?
5 M
6(d)
An apple, a banana, a mango, and an orange are to be distributed to four boys B1, B2, B3, B4. The boys B1 and B2 do not wish to have apple, the boy B3 does not want banana or mango, and B4 refluses orange. In how many ways the distribution can be made so that no boy is displeased?
5 M
7(a)
Using the generating functions, find the number of i) non negative, and ii) positive, integer solutions of the equation x1 + x2 + x3 + x4 = 25.
6 M
7(b)
A bag contains a large number of red, green, white and black marbles, with atleast 24 of each colour. In how many ways can one select 24 og these marbles, so that there are even number of white marbles and atleast six black marbles.
7 M
7(c)
Using exponential generating function, find the number of ways in which four of the letters in the word ENGINE be arranged
7 M
8(a)
Solve the recurrence relation.
an = 2ah/2 + (n-1) for n = 2k, k ≥ 1, given a1 = 0.
an = 2ah/2 + (n-1) for n = 2k, k ≥ 1, given a1 = 0.
8 M
8(b)
The number of virus affected files in a system is 1000 (to start with) and this increase 250% every two hours. Using a recurrence relation determine the number of virus affected files in the system after one day.
5 M
8(c)
Find and solve a recurrence relation for the number of binary sequences of length n ≥ 1 that have no consecutive O's.
7 M
More question papers from Graph Theory and its Applications