STUPIDSID
1 (a)
Define and give an example for each of the following: -
i) Connected graph
ii) Spanning subgraph
ii) Complement of a graph
i) Connected graph
ii) Spanning subgraph
ii) Complement of a graph
6 M
1 (b)
Define isomorphism. Show that the following graphs are isomorphism.
7 M
1 (c)
In the graph given below find the number of paths from V1 V2. How many of these paths have length 5.
7 M
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.
7 M
2 (b)
Prove that Peterson graph is non-planar.
6 M
2 (c)
Define chromatic number of a graph. Find the chromatic polynomial for the graph shown below and also find the chromatic number for the same.
7 M
3 (a)
Define and give an example for each of the following:
i) Rooted tree
ii) Complete binary tree
iii) Balanced tree
i) Rooted tree
ii) Complete binary tree
iii) Balanced tree
6 M
3 (b)
Construct an optimal prefix code for the symbols a, o, q, u, y, z that occur with the frequencies 20, 28, 4, 17, 12, 7 respectively.
7 M
3 (c)
Obtain the optimal prefix code for the message "ROAD IS GOOD". Indicate the code.
7 M
4 (a)
For the network shown below, determine the maximum flow between the vertices A and D by identifying the cutset of minimum capacity.
7 M
4 (b)
State and prove max-flow and min-cut theorem.
6 M
4 (c)
Apply PRIMS algorithm to determine a minimal spanning tree for the weighted graph shown below.
7 M
5 (a)
State and explain product rule of counting along with an example.
4 M
5 (b)
Find the co-efficient of:
i) x9y3 in the expansion of (2x-3y)12
ii) x9 in the expansion (3x2 - 2/x)15.
i) x9y3 in the expansion of (2x-3y)12
ii) x9 in the expansion (3x2 - 2/x)15.
8 M
5 (c)
i) From seven consonants and five vowels how many sets consisting of four different consonants and three different vowels can be formed.
ii) Find the number of arrangement of the letters in TALLAHASSEE which have no adjacent A's.
ii) Find the number of arrangement of the letters in TALLAHASSEE which have no adjacent A's.
8 M
6 (a)
Out of 30 students in hostel, 15 study history, 8 study economics and 6 study geography. It is know that 3 students all these subjects. Show that 7 or more students study none of these subjects,
6 M
6 (b)
Find the number of derangements pf the integers from 1 to 2n satisfying the condition that the elements in the first n-places are:
i) 1, 2, 3, ......, n in some order
ii) n+1, n+2, ........., 2n in some order.
i) 1, 2, 3, ......, n in some order
ii) n+1, n+2, ........., 2n in some order.
6 M
6 (c)
What is the expansion formula for rook-polynomials? Find the rook polynomial for the 3×3 board by using the expansion formula.
8 M
7 (a)
i) Find a generating function for the following sequence, 02, 12, 22, 32 .......
ii) Find the co-efficient of x27 in the expansion of the following functions.
(x4+2x5+3x6+......)5.
ii) Find the co-efficient of x27 in the expansion of the following functions.
(x4+2x5+3x6+......)5.
6 M
7 (b)
Using generating function, find the number of partitions of n=6.
7 M
7 (c)
Define an exponential generating function. Find the exponential function for the number of ways to arrange n-letter n≥0, selected for each of the following words.
i) HAWAII
ii) MISSISSIPPI
iii) ISOMORPHISM
i) HAWAII
ii) MISSISSIPPI
iii) ISOMORPHISM
7 M
8 (a)
Solve the recurrence relation (Fibonacci relation).
Fn+2=Fn+1+Fn given F0=0 and F1=1 and n≥0
Fn+2=Fn+1+Fn given F0=0 and F1=1 and n≥0
6 M
8 (b)
Solve the recurrence relation
a n+3 -3an+2 + 3an+1 - an=3 +5n for n≥0
a n+3 -3an+2 + 3an+1 - an=3 +5n for n≥0
7 M
8 (c)
Find a generating function for the recurrence relation
an+2-3an+1+2an=0, n≥0 and a0=1, a1=6. Hence solve it.
an+2-3an+1+2an=0, n≥0 and a0=1, a1=6. Hence solve it.
7 M
More question papers from Graph Theory and its Applications