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

(C) 27 (D) None of the above.
18. In the directed network in Figure one 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.
19. A self dual connected 3-regular planar graph with exactly e edges exists
(A) when e =10 but not when e = eight (B) both when e = 10 and e = 8
(C) neither when e = 10 nor when e = eight (D) when e = eight but not when e = 10.
20. The total number of non-isomorphic self complementary simple bipartite graphs is
(A) 0 (B) 1
(C) two (D) None of the above.
21. A graph with 12 vertices and 31 edges have vertices of degree four and six only. Then the number of vertices of degree four is
(A) seven (B) 5
(C ) not determinable (D) none of the above.


B
22. The total number of non-isomorphic 7-regular simple graphs on 10 vertices is
(A) 0 (B) 4
(C) eight (D) None of the above.
23. The pair (m, n) for which there exists a binary tree on 55 vertices of height m but not of height n is
(A) (22, 6) but not (4, 27) (B) ( 4, 27) but not (22,6)
(C) Both the above pairs (D) None of the above pairs.
24. Consider the statements for a simple graph G : (I) If G has an Euler line then G has a unicursal line, (II) If G has a Hamiltonian cycle then G has a Hamiltonian path.
(A) Both (I) and (II) are accurate (B) (I) is accurate but (II) is incorrect

Earning:   Approval pending.