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

(C) both of these possibilities (D) none of these possibilities.
14. In the directed network in Figure two above, if S = {s, a, d}, T = {b, c, t} then the capacity of the (s, t) –cut (S, T) is
(A) 35 (B) 39
(C) 37 (D) None of the above.
15. In the digraph in Figure 2, suppose any edge is assigned weight equal to the 1st integer in its tag. Then shortest path from s to t has distance
(A) 14 (B) 28
(C) 27 (D) None of the above.

B
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.










16. Suppose the digraph in Figure one denotes a directed network where for the tag cu,v, fu,v of the directed edge (u, v), cu,v denotes its capacity and F = { fu,v : (u, v) is an edge} is an (s, t) –flow for these capacities. Then which possibilities are allowed?
(A) y = 3, z = four (B) y = 4, z = 5
(C) both of these possibilities (D) none of these possibilities.
17. In the digraph in Figure 1, suppose any edge is assigned weight equal to the 1st integer in its tag. Then shortest path from s to t has distance
(A) 14 (B) 28

Earning:   Approval pending.