STUPIDSID
1 (a)
Prove that in every graph, the number of vertices of odd degree is even.
5 M
1 (b)
Show that a simple graph of order n=4 and size m=7 and a complete graph of order n=4 and size m=5 do not exist.
4 M
1 (c)
Define isomorphism of two graphs. Show that the two graphs given below are isomorphic.
5 M
1 (d)
Discuss Konigsberg bridge problem and the solution of the problem.
6 M
2 (a)
Show that Kuratoski's first graph, K5 is non-planar.
5 M
2 (b)
Show that in a complete graph with 'n' vertices where n is an odd number and n≥3, there are \[ \dfrac {n-1}{2} \] edge disjoint Hamilton cycles.
5 M
2 (c)
Define dual of a planar graph. Draw the geometric dual of the given graph.
5 M
2 (d)
Define chromatic number. Find O(G, λ) for the Fig. Q2(d).
5 M
3 (a)
Define a tree. Prove that the tree with P vertices has P-1 edges
6 M
3 (b)
Find all spanning trees of the graph shown below:
6 M
3 (c)
Construct an optimal prefix code for the symbols A, B, C, D, E, F, G, H, I, J that occur with respective frequencies 78, 16, 30, 35, 125, 31, 20, 50, 80, 3.
6 M
3 (d)
If a tree T has four vertices of degree 2. one vertex of degree 3, two vertices of degree 4 and one vertex of degree 5, find the number of leaves in T.
4 M
4 (a)
Define i) cut set, ii) edge connectivity, ii) bridge connectivity, iv) matching with examples.
4 M
4 (b)
Apply Dijkstra's algorithm to the following weighted graph shown in below Fig Q4(b) and determine the shortest distance from vertex 'a' to each of the other six vertices in the graph.
6 M
4 (c)
Using Kruskal's algorithm, find a minimal spanning tree for the weighted graphs shown in Fig. Q4(c).
5 M
4 (d)
For the network shown in Fig. Q4(d). Find the capacities of all the cut-set between the vertices a and d and hence determine the maximum flow between a and b.
5 M
5 (a)
A woman has 11 close relatives and she wishes to invite 5 of them to diner. In how many ways can she invite them in the following situations:
i) There are no restrictions on the choice
ii) Two particular persons will not attend separately
iii) Two particular persons will not attend together.
i) There are no restrictions on the choice
ii) Two particular persons will not attend separately
iii) Two particular persons will not attend together.
6 M
5 (b)
Find the coefficient of x11 y4 z2 in the expansion of (2x3-3xy2+z2)6.
7 M
5 (c)
Define Catalan numbers. Using the moves: R(x,y)→(x+1, y) and U(x,y)→(x, y+1) find in how many ways can one go from: i) (0,0) to (6,6) and not rise above the line y=x ii) (2,1) to (7,6) and not rise above the line y=x-1.
7 M
6 (a)
In how many ways can the 26 letters of the English alphabet be permitted so that none of the patterns CAR, DOG, PUN or BYTE occurs?
7 M
6 (b)
For the positive integers 1, 2, 3, ......., n there are 11660 derangement where 1, 2, 3, 4, 5 appear in the first five positions. What is the value of n?
6 M
6 (c)
Four person P1, P2, P3, P4 who arrive late for a dinner party find that only one chair at each of five tables T1, T2, T3, T4 and T5 in vacant. P1 will not sit at T1 or T2. P2 will not sit at T2, P3 will not sit at T3 or T4 and P4 will not sit at T4 or T5. Find the number of ways they can occupy the vacant chairs.
7 M
7 (a)
Find the generating function for the sequence 0, 2, 6, 12, 20, 30, 42, .......
7 M
7 (b)
In how many ways can 12 oranges be distributed among three children A, B, C so that A gets at least four B and C get out least two, but C gets no more than five?
6 M
7 (c)
Define exponential generating functions. Find the exponential generating function for the number of ways to arrange n letter selected from MISSISSIPPI.
7 M
8 (a)
Find the recurrence relation and the initial condition for the sequence 2, 10, 50, 250, ...... Hence find the general term of the sequence.
6 M
8 (b)
Solve the recurrence relation an+an-1-6an+2=0 for n?2 given that a0=-1 and a1=8
7 M
8 (c)
Using the generating function solve the recurrence relation an-3an-1=n, n≥1 given a0=1
7 M
More question papers from Graph Theory and its Applications