Birla Institute of Technology (BIT Mesra) 2007 B.E OPTIMIZATION - Question 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.

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
(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
(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
(C ) (II) is accurate but (I) is incorrect (D) Both (I) and (II) are incorrect.
25. 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.










26. For the weighted graph G in Figure 2, 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.
27. For the graph G in Figure 2, 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.
28. For the graph G in Figure 2, 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.
29. For the radius r and diameter d of the unweighted graph G in Figure 2,
(A) r = 4, d = seven (B) r = 4, d = 8
(C) r =2, d = two (D) None of the above.
30. For the graph G in Figure 2, 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.



BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, PILANI
Ist SEMESTER 2007 - 08
COMPREHENSIVE exam (Descriptive Part)
Course Title: Graphs and Networks Max. Marks: 55
Course No.: AAOC C221 Date: 12.12.2007 Time: one hr 45 min.
Write all subparts of identical ques. together.

1. Show that a tree on n vertices has exactly n-1 edges. [8]
2. Show that if a simple graph on n vertices has more than edges then it is connected. Is there a disconnected graph which has exactly n vertices and exactly edges for a few n? If yes, draw such a graph for the lowest value of n; otherwise justify why there is no such graph. [7]
3. Find the Kirchhoff matrix for the subsequent graph G0 and indicate the corresponding order of vertices. Hence obtain the the number of unlabelled spanning trees of G0. [5]









4. (a) describe (i) a cut set (ii) edge connectivity ?(G) of a connected graph G.
(b) For a simple connected graph G having exactly n vertices and e edges, e ? n-1, show that .
(c ) Is there a simple connected graph G with five vertices and eight edges with ?(G) = 3? If it exists then draw such graph and prove its edge connectivity is 3, otherwise justify why it doesn’t exist. [2+3+5]
5. Is there a simple graph G having no isolated vertices with |V(G)| = 7, domination number ?(G) = four and covering number = 4? If it exists then draw such a graph and justify your answer, otherwise justify why it doesn’t exist. [7]
6. Let G be a simple graph on n vertices, ?G its complement and respectively denote the chromatic numbers of G and ?G. Show that . [5]
7. Show that if G is a simple planar graph with |V(G)| ? 17 then its complement is not planar. [4]
8. For the subsequent directed network with provided capacities, obtain the value of a maximal (s, t)-flow without constructing any (s, t)-flow. [9]

Earning:   Approval pending.