Name of the College : Government Engineering College
Department : Computer Science Engineering
Subject Code/Name : P08 CH – 12/GRAPH THEORY AND COMBINATORICS
Year : May 2013
Degree : B.Tech
Sem : VI
Website : gecwyd.ac.in
Document Type : Model Question Paper
Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/pescemandya.org/4699-s6_cse_ns_may_2013.pdf
Graph Theory & Combinatorics :
Vl Semester B.Tech. Degree (Reg./Sup./lmp. – lncluding Part Time) Examination, May 2013
(2AA7 Admn. Onwards)
Related : Government Engineering College Microprocessors & Microcontrollers B.Tech Question Paper : www.pdfquestion.in/4704.html
Time : 3 Hours
Max. Marks : 100
l. a) Write short notes on multi graph, closed graph and loop free graph.
b) Prove that, for any undirected graph or multi graph G, the number of vertices of odd degree must be even.
c) Prove that if G = (V, E) is an undirected graph, then G is connected if and only if G has a spanning tree.
d) Write short notes on prefix code, full binary tree and complete binary tree. Give suitable examples for each.
e) Write notes on the rules of sum and product. Give examples for the same.
f) Define Binomial theorem.
g) Define generating functions. Give suitable examples.
h) Write short notes on non-homogeneous recurrence relations. (8×5=40)
ll. a) Explain in detail with suitable examples, isomorphic graphs and complete graphs. 10
b) Write notes on sub graph, spanning sub graph and induced sub graph.
OR
c) Define Euler circuit an Euler trail. Prove that for an undirected graph or multi graph G = (V, E) with no isolated vertices, then G has a Euler circuit if and only if G is connected and every vertex of G has even degree. 11
d) Define Planar Graphs. Give examples. 4
a) Explain in detail with suitable examples, the Dijkstra’s shortest path Algorithm. 15
OR
b) Write short notes on Prim’s algorithm. Also prove the following : Let G = (V, E) be a loop-free weighted connected undirected graph. Any spanning tree for G that is obtained by Prim’s algorithm is optimal. 15
lV. a) Write short notes on permutations and combinations. Give examples for both. 10
b) Find out the number of possible 15 letter sequence allowed in the word ‘ALGORITHM’, if the repetitions of letters are allowed. 5
OR
c) Explain in detail the principles of Inclusion and Exclusion.
d) ln how many ways in which we can arrange 40 boys and 20 giris in 5 groups of 12 members each, so that each group contains at least one girl.
V. a) Write short notes on the exponential generating function.
b) A ship carries 48 flags, 12 each of colours red, white, blue and black . 12 ot these poles are placed on a vertical pole in order to communicate with other ships.
i) How many of these signals use an even number of blue flags and odd number of black flags ?
ii) How many of these signals have at least three white flags or no white flags ?
OR
Explain in detail with suitable examples the first order linear recurrence relations and the second order linear homogeneous recurrence relations with constant coefficients.
Explain in detail the method of generating functions with suitable example.
Engineering Graphics : (For CS/IT Branches)
Time : 3 Hours
instructions :
1) Answer all questions.
2) Missing dimensions may suitably assumed.
1. a) The top view of a line AB, 80 mm long measures 65 mm and length of the front view is 50 mm. The end A is on HP and 15 mm infront of VP. Draw the projection of AB and determine its inclinations with Hp and Vp. n
OR
2. a) A cone of base 60 mm diameter and axis 80 mm long is lying with one of its generators on HP and the axis appears to be inclined to the VP at an angle of 40″ in the top view. Draw its projection.
A square pyramid of 50 mm edges of base and height 70 mm rests on its base on HP with one of its base edges parallel to VP. lt is cut by an inclined section plane in such a way that the true shape of section is trapezium whose parallel sides measure 40 mm and 20 mm. Draw its front view, sectional top view and the true shape of section.
OR
b) A vertical pentagonal prism 30 mm side of base and height 60 mm has one of its rectangular faces parallel to VP and nearer to it. A thorough square hole of 25 mm sides is made in the centre of the prism such that the axis of the hole bisects the axis of the prism at right angles. The edges of the hole are equally inclined to HP. Draw the development of the prism showing the shape of the hole produced by it.