Visvesvaraya Technological University (VTU) 2006 B.E Computer Science 06CS42 Graph Theory & Combinatorics - Question Paper

Fourth Semester B.E Degree exam
(Common to CS and IS)
Model ques. Paper
06CS42 Graph Theory & Combinatorics
Note: ans any 5 Full questions, selecting at lowest 2 ques. from
every PART
Time: three Hours Maximum marks : 100
PART A
1a) describe Isomorphism of graphs. Show that the subsequent graphs are isomorphic (6)
Fig 1a
b) Show that a graph has even number of odd vertices (6)
c) describe the subsequent terms with examples (8)
i) Circuit ii) Path iii) Directed Graphs iv) Sub graph
2 a) describe a planar graph. Show that K5 is not a planar graph (6)
b) Show that in any connected planar graph with n vertices, e edges and f faces
e-n+2=f (Euler’s Formula) (7)
c) i) What is Hamilton cycle?
ii) For n€Z+ , n=2 show that the number of distinct Hamilton cycles in the graph
Kn, n is ½(n-1)!n!
iii) How many various Hamilton’s paths are there for Kn,n and n=1?
(1+3+3 = 7)
3 a) Show that a Tree with ‘n’ vertices has n-1 edges (6)
b) find a Prefix code to send the message ROAD IS GOOD using tagged binary
tree and hence encode the message (7)
c) Apply merge-sort to the list: -1,7,4,11,5,-8,15,-3,-2,6,10,3 (7)
4 a) State Kruskal’s algorithm and using this algorithm obtain a minimal spanning
tree for the weighted graph shown beneath (7)
3
2 2
Fig. 4a
b) discuss Max-Flow, Min-Cut theorem. Apply this to the subsequent transport
network to find the Max-flow. (8)
c) discuss the steps in Dijikstra’s Shortest Path Algorithm. (5)
PART B
5 a) A Computer Science Professor has 7 various Programming books on a
bookshelf. 3 of them deal with C++, the other 4 with Java. In how many
ways can the Professor organize these books on the shelf (8)
i) If there are no restrictions.
ii) If the languages should alternate
iii) If all the C++ books must be next to every other.
iv) If all the C++ books must be next to every other and all the Java
books must be next to every other
b) discuss the Binomial Theorem. find the Coefficient of xyz2 in the expansion
of (2x-y-z)4 (5)
F
C
D
B
A
E
3
5
2 4
3
5
4
2,10
5,5
9,0
2,2
a
3,3
d
c
z
b
c) describe Catalan Number. In how many ways can 1 organize 3 1’s and
three –1s’s so that all the 6 partial sums (starting with the 1st summand)
are non negative? List all the arrangements. (7)
6 a) In how many ways can 1 organize the letters in CORRESPONDENTS so that
i) There are exactly 2 pairs of consecutive identical letters
ii) There are at lowest 3 pair of consecutive identical letters. (8)
b) In how many ways can the integers 1,2,3..10 be organizes in a line so that no
even integer is in its natural place (5)
c) An apple, a banana, a mango and an orange are to be distributed to 4 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 returns orange. In how many ways the
distribution can be made so that no boy is displeased? (7)
7. a) Determine the Coefficient of X8 in 1/(x-3)(x-2)2 (7)
b) Determine the sequence generated by exponential generating function
e2x – 3x3 + 5x2 + 7x (7)
c) obtain all the partials of seven (6)
8. a) Solve Linear recurrence relation.
Cn = 3Cn-1 -2Cn-2 with C1 = 5, C2 = three (6)
b) obtain the generating function of an + an-1 -6an-2 for n>=2, a0=-1 and a1=8 (7)
c) obtain the generating function of ar + 5ar-1 + 6ar-2 = 3r2 (7)

Earning:   Approval pending.