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

A
7. The total number of non-isomorphic self complementary simple bipartite graphs is
(A) 0 (B) 1
(C) two (D) None of the above.
8. 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.
9. 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.
10. 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.
11. 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
(C ) (II) is accurate but (I) is incorrect (D) Both (I) and (II) are incorrect.
12. 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.











13. Suppose the digraph in Figure two 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

Earning:   Approval pending.