STUPIDSID
1 (a)
Define graph isomorphism and isomorphic graphs. Determine whether the following graphs are isomorphic or not:
5 M
1 (b)
Define complement of a simple graph. Let G be a simple graph of order n. If the size of G is 56 and the size of G is 80. What is n?
5 M
1 (c)
Let G=(V,E) be a connected undirected graph. What is the largest possible values for |V| if |E|=19 and deg(v)?4 for all v ∈ V?
4 M
1 (d)
Write a note on "Konigsberg bridge problem and its solution".
6 M
2 (a)
Define planar graph. Prove that the Peterson graph is nonplanar.
5 M
2 (b)
Define Hamilton cycle. How many edge disjoint Hamilton cycle exist in the complete graph seven vertices? Also draw the graph to show these Hamilton cycle.
5 M
2 (c)
Define dual of a planar graph. Construct the dual of the planar graph given below.
4 M
2 (d)
Define chromatic number and chromatic polynomial. Determine the chromatic polynomial for the graph shown below
6 M
3 (a)
A class room contains 10 micro computer that are to be connected to a wall socket that has 2 outlets. Connections are made by using extension cords that have 2 outlets each. Find the least number of cords needed to get these computer set up for use.
4 M
3 (b)
Apply merge sort to the list -1, 0, 2, -2, 3, 6, -3, 5, 1, 4.
4 M
3 (c)
Find all the spanning trees of the graph shown below. Also find all the non isomorphic spanning trees.
6 M
3 (d)
Obtain an optimal prefix code for the message MISSION SUCCESSFUL. Indicate the code for the message.
6 M
4 (a)
State Kruskal's algorithm. Using Kruskal's algorithm find a minimal spanning tree for the weighted graph given below.
8 M
4 (b)
Apply Dijkstra's algorithm the diagram shown in Fig. Q4(b) and determine the shortest distance from vertex a to each of the other vertices in the directed graph.
6 M
4 (c)
Define the following with one example for each: i) cut set
ii) Edge connectivity
iii) Vertex connectivity.
ii) Edge connectivity
iii) Vertex connectivity.
6 M
5 (a)
A bit is either 0 or 1. A byte is a sequence of 8 bits. Find: i) The number of bytes; ii) The number of bytes that begin with 11 and end 11; iii) the number of bytes that begin with 11 and do not end with 11 and iv) the number of bytes that begin 11 or end with 11.
6 M
5 (b)
How many arrangement of the letters in MISSISSIPPI have no consecutive S's?
5 M
5 (c)
Find the coefficient of x9 in the expansion of \[ 3\left ( x^2 - \dfrac {2}{x} \right )^{15} \]
5 M
5 (d)
In how many ways can we distribute 7 apples and 6 oranges among 4 children so that each child gets at least 1 apple?
4 M
6 (a)
How many integers between 1 and 300 (inclusive) are
i) Divisible by at least one of 5, 6, 8?
ii) Divisible by none of 5, 6, 8?
i) Divisible by at least one of 5, 6, 8?
ii) Divisible by none of 5, 6, 8?
6 M
6 (b)
Define derangement. Find the number of derangement of 1, 2, 3, 4. List all the derangements.
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?
8 M
7 (a)
Find the generating function for the sequence 8, 26, 54, 92, ......
6 M
7 (b)
Using generating function, find the number of i) non negative and ii) positive integer solutions of the equation x1+x2+x3+x4=25.
8 M
7 (c)
Define exponential generating functions using exponential generating function find the number of ways in which 5 of the letters in the word CALCULUS be arranged.
6 M
8 (a)
The number of bacteria in culture is 1000 (approximately) and this number increase 250% every two hours. Use a recurrence relation to determine the number of bacteria present after one day.
5 M
8 (b)
Solve the recurrence relation
an+2-4an+1=-200, n≥0 and a0=3000, a1=3300.
an+2-4an+1=-200, n≥0 and a0=3000, a1=3300.
7 M
8 (c)
Find the generating function for the recurrence relation an+1-an=n2, n≥0 and a0=1.
8 M
More question papers from Graph Theory and its Applications