STUPIDSID
1 (a)
i) Define a connected graph. Give an example of a connected graph G where removing any edge of G results in a disconnected graphs.
ii) Define complement of a graph. Find an example of a self-complementary graph on four vertices and one on five vertices.
ii) Define complement of a graph. Find an example of a self-complementary graph on four vertices and one on five vertices.
6 M
1 (b)
Find all (loop-free) non-isomorphic undirected graphs with four vertices. How many of these graphs are connected?
5 M
1 (c)
Show that the following graphs in Fig Q1(c) are isomorphic:
5 M
1 (d)
How many different paths of length 2 are there in the undirected graph G in Fig. Q1(d)?
4 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.
6 M
2 (b)
Define Planar graph. Let G=(V, E) be a connected planar graph or multigraph with |V|=V and |E|=e. Let r be the number of region in the plane determined by a planar embedding 0+G. Then prove that v-e+r=2.
7 M
2 (c)
i) Find the chromatic number of the complete bipartite graph Km,n and a cycle, Cn on n vertices n≥3.
ii) Determine the chromatic polynomial for the graph G in Fig. Q2(c).
ii) Determine the chromatic polynomial for the graph G in Fig. Q2(c).
7 M
3 (a)
i) Prove that in every tree T=(V,E), |E|=|V|-1.
ii) Let F1=(V1, E1) be a forest of seven trees, where |E1|=40. What is |V1|?
ii) Let F1=(V1, E1) be a forest of seven trees, where |E1|=40. What is |V1|?
7 M
3 (b)
Define: i) Spanning tree ii) Binary rooted tree. Find all the non-isomorphic spanning trees of the graph Fig. Q3(b).
6 M
3 (c)
Define prefix code. Obtain an optimal prefix code for the message ROAD IS GOOD. Indicate the code.
7 M
4 (a)
Apply Dijkstra's algorithm to the digraph shown in Fig. Q4(a) and determine the shortest distance from vertex a to each of the other vertices in the graph.
7 M
4 (b)
Define the following with respect to graph: i) matching ii) a cut-set. Show that the graph in Fig. Q4(b) has a complete matching from V1 to V2. Obtain two complete matching.
7 M
4 (c)
For the network shown below, find the capacities of all the cutsets between A and D, and hence determine the maximum flow between A and D.
6 M
5 (a)
How many arrangement of the letters in MISSISSIPPI have to consecutive S's?
5 M
5 (b)
i) Find the coefficient of v2w4xz in the expansion of (3v+2w+x+y+z)8
ii) How many distinct terms arise in the expansion in part (i)?
ii) How many distinct terms arise in the expansion in part (i)?
5 M
5 (c)
How many positive integers n can we form using the digits 3,4,5,5,6,7 if we want n to exceed 5000000?
5 M
5 (d)
A message is made up of 12 different symbols and is to be transmitted through a communication channel. In addition to the 12 symbols, the transmitter will also send a total of 45 blank spaces between the symbols, with at least three spaces between each pair of consecutive symbols. In how many ways the transmitter sends such message?
5 M
6 (a)
In how many ways can the 26 letters of the alphabet be permuted so that none of the patterns spin, game, path or net occurs?
7 M
6 (b)
Define derangement. In how many ways can each of 10 people select a left glove and a right glove out of a total of 10 pairs of gloves so that no person selects a matching pair of gloves?
6 M
6 (c)
Five teachers T1, T2, T3, T4, T5 are to be made class teachers for five classes C1, C2, C3, C4, C5 one teacher for each class T1 and T2 do not wish to become the class teachers for C1 or C2, T3 and T4 for C4 or C5 and T5 for C3 or C4 or C5. In how many ways can the teacher be assigned the work?
7 M
7 (a)
Find the generating function for the following sequences:
i) 12, 22, 32, 42, ......
ii) 02, 12, 22, 32, ......
ii) 0, 2, 6 12, 30, .....
i) 12, 22, 32, 42, ......
ii) 02, 12, 22, 32, ......
ii) 0, 2, 6 12, 30, .....
6 M
7 (b)
Use generating function to determine how many four element subset of S={1, 2, 3, ....., 15} contain to consecutive integers?
7 M
7 (c)
Using exponential generating function, find the number of ways in which 4 of the letters in the words given below be arranged: i) ENGINE
ii) HAWAII
ii) HAWAII
7 M
8 (a)
The number of virus affected files in a system is 1000 (to star with) and this number increase 250% every two hours. Use a recurrence relation to determine the number of virus affected files in the system after one day.
5 M
8 (b)
Solve the recurrence relation:
an+2-10an+1+21an=3n2-2, n?0
an+2-10an+1+21an=3n2-2, n?0
7 M
8 (c)
Using the generating function method, solve the recurrence relation,
an-3an-1=n, n≥1 given a0=1
an-3an-1=n, n≥1 given a0=1
8 M
More question papers from Graph Theory and its Applications