Birla Institute of Technology (BIT Mesra) 2007 B.E OPTIMIZATION - exam paper

BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, PILANI
Ist SEMESTER 2007 - 08
COMPREHENSIVE exam (Quiz Part)
Course Title: Graphs and Networks Max. Marks: 45
Course No.: AAOC C221 Date: 12.12.2007 Time: one hr 15 min.

Name : Id. No. :
NOTE : In the table below, write the tag of accurate ans for every ques.. every accurate ans carries three marks, every wrong ans carries –1 marks. No cutting or overwriting is allowed. ques. with cutting or overwriting will be treated as unattempted. Rough work can be done in the main ans sheet and later crossed. Nothing else should be written on ques. paper.
Q. no 1 2 3 4 5 6 7 8
Ans.

Q. No. 9 10 11 12 13 14 15
Ans.










1. For the weighted graph G in Figure 1, let x be the weight of a minimal spanning tree and y be the weight of a maximal spanning tree. Then
(A) x = 9, y = 26 (B) x = 9, y = 25
(C) x= 10, y = 26 (D) None of the above.
2. For the radius r and diameter d of the unweighted graph G in Figure 1,
(A) r = 4, d = seven (B) r = 4, d = 8
(C) r =2, d = two (D) None of the above.
3. For the graph G in Figure 1, Let x denote the maximum number of vertex disjoint paths from A to H and y denote the maximum number of edge disjoint paths from A to H. Then
(A) x = 3, y= three (B) x = 4, y = 3
(C) x =3, y =4 (D) None of the above.
4. For the graph G in Figure 1, if ?(G) denote the chromatic number of G and c(G) denotes the covering number of G then
(A) ?(G) = 3, c(G) =4 (B) ?(G) = 4, c(G) =4
(C) ?(G) = 3, c(G) =7 (D) None of the above.
5. For the graph G in Figure 1, let S be a largest subset of V(G) which is both dominating as well as independent. Then
(A) S does not exist (B) |S| = 0
(C) |S| = two (D) None of the above.
6. Let G1 = K42, 41 and G2 = K45, 62. Then which graphs have a Hamiltonian path?
(A) both G1 and G2 (B) G1 but not G2
(C) G2 but not G1 (D) neither G1 nor G2.

Earning:   Approval pending.