1. Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
Correct : B. sum of degrees of vertices in u = sum of degrees of vertices in v
2. A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
Correct : A. number of vertices in u=number of vertices in v
3. A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
Correct : B. n/2
4. When is a graph said to be bipartite?
Correct : A. if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b
5. Are trees bipartite?
Correct : A. yes
6. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
Correct : A. 100
7. Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?
Correct : A. yes
8. Can there exist a graph which is both eulerian and is bipartite?
Correct : A. yes
9. A graph is found to be 2 colorable. What can be said about that graph?
Correct : B. the given graph is bipartite
10. Which type of graph has no odd cycle in it?
Correct : A. bipartite
11. What type of graph has chromatic number less than or equal to 2?
Correct : B. bipartite
12. Which of the following is the correct type of spectrum of the bipartite graph?
Correct : A. symmetric
13. Which of the following is not a property of the bipartite graph?
Correct : D. asymmetric spectrum
14. Which one of the following is the chromatic number of bipartite graph?
Correct : A. 1
15. Which graph has a size of minimum vertex cover equal to maximum matching?
Correct : D. bipartite
16. Which theorem gives the relation between the minimum vertex cover and maximum matching?
Correct : A. konig’s theorem
17. Which of the following is not a property of perfect graph?
Correct : D. line graph
18. Which of the following has maximum clique size 2?
Correct : A. perfect graph
19. What is the chromatic number of compliment of line graph of bipartite graph?
Correct : C. 2
20. What is the clique size of the line graph of bipartite graph?
Correct : C. 2
21. It is possible to have a negative chromatic number of bipartite graph.
Correct : B. false
22. Every Perfect graph has forbidden graph characterization.
Correct : A. true
23. Which structure can be modelled by using Bipartite graph?
Correct : A. hypergraph
24. Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
Correct : B. complete bipartite
25. Which graph is also known as biclique?
Correct : B. complete bipartite
26. Which term defines all the complete bipartite graph that are trees?
Correct : D. stars
27. How many edges does a n vertex triangle free graph contains?
Correct : C. n2 / 4
28. Which graph is used to define the claw free graph?
Correct : B. claw graph
29. What is testing of a complete bipartite subgraph in a bipartite graph problem called?
Correct : D. np-complete problem
30. Which graph cannot contain K3, 3 as a minor of graph?
Correct : A. planar graph
31. Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph?
Correct : D. nm
32. Which complete graph is not present in minor of Outer Planar Graph?
Correct : C. k3, 2
33. Is every complete bipartite graph a Moore Graph.
Correct : A. true
34. What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value?
Correct : B. n + m – 2
35. Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph?
Correct : D. n*m
36. What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value?
Correct : B. m-1
37. Is it true that every complete bipartite graph is a modular graph.
Correct : A. true
38. How many spanning trees does a complete bipartite graph contain?
Correct : B. mn-1 * nn-1
39. What does Maximum flow problem involve?
Correct : A. finding a flow between source and sink that is maximum
40. A network can have only one source and one sink.
Correct : B. true
41. What is the source?
Correct : A. vertex with no incoming edges
42. Which algorithm is used to solve a maximum flow problem?
Correct : D. ford-fulkerson algorithm
43. Does Ford- Fulkerson algorithm use the idea of?
Correct : B. residual graphs
44. The first step in the naïve greedy algorithm is?
Correct : A. analysing the zero flow
45. Under what condition can a vertex combine and distribute flow in any manner?
Correct : B. it should maintain flow conservation
46. Find the maximum flow from the following graph.
Correct : C. 15
47. A simple acyclic path between source and sink which pass through only positive weighted edges is called?
Correct : A. augmenting path
48. Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm.
Correct : A. true
49. Who is the formulator of Maximum flow problem?
Correct : B. t.e. harris and f.s. ross
50. How many constraints does flow have?
Correct : C. two
51. Stable marriage problem is an example of?
Correct : B. backtracking algorithm
52. Which of the following algorithms does Stable marriage problem uses?
Correct : A. gale-shapley algorithm
53. An optimal solution satisfying men’s preferences is said to be?
Correct : A. man optimal
54. When a free man proposes to an available woman, which of the following happens?
Correct : D. she will accept
55. If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.
Correct : A. true
56. How many 2*2 matrices are used in this problem?
Correct : B. 2
57. What happens when a free man approaches a married woman?
Correct : C. she goes through her preference list and accordingly, she replaces her current mate with him
58. In case of stability, how many symmetric possibilities of trouble can occur?
Correct : B. 2
59. Which of the following happens?
Correct : A. w2 replaces m1 with m2
60. Who formulated a straight forward backtracking scheme for stable marriage problem?
Correct : A. mcvitie and wilson
61. Can stable marriage cannot be solved using branch and bound algorithm.
Correct : B. false
62. What is the prime task of the stable marriage problem?
Correct : C. to determine stability of marriage
63. Which of the following problems is related to stable marriage problem?
Correct : A. choice of school by students
64. What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?
Correct : C. o(n2)
65. is a matching with the largest number of edges.
Correct : A. maximum bipartite matching
66. Maximum matching is also called as maximum cardinality matching.
Correct : A. true
67. How many colours are used in a bipartite graph?
Correct : B. 2
68. What is the simplest method to prove that a graph is bipartite?
Correct : C. it does not have a cycle of an odd length
69. A matching that matches all the vertices of a graph is called?
Correct : A. perfect matching
70. What is the length of an augmenting path?
Correct : B. odd
71. In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?
Correct : C. augmenting
72. A matching M is maximal if and only if there exists no augmenting path with respect to M.
Correct : A. true
73. Which one of the following is an application for matching?
Correct : B. pairing boys and girls for a dance
74. Which is the correct technique for finding a maximum matching in a graph?
Correct : B. bfs traversal
75. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
Correct : C. maximum weight matching
76. Who was the first person to solve the maximum matching problem?
Correct : A. jack edmonds
77. From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?
Correct : A. 5
78. The worst-case efficiency of solving a problem in polynomial time is?
Correct : A. o(p(n))
79. Problems that can be solved in polynomial time are known as?
Correct : B. tractable
80. The sum and composition of two polynomials are always polynomials.
Correct : A. true
81. is the class of decision problems that can be solved by non- deterministic polynomial algorithms?
Correct : A. np
82. Problems that cannot be solved by any algorithm are called?
Correct : C. undecidable problems
83. The Euler’s circuit problem can be solved in?
Correct : D. o(n2)
84. To which class does the Euler’s circuit problem belong?
Correct : A. p class
85. Halting problem is an example for?
Correct : B. undecidable problem
86. How many stages of procedure does a non- deterministic algorithm consist of?
Correct : B. 2
87. A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial.
Correct : A. true
88. How many conditions have to be met if an NP- complete problem is polynomially reducible?
Correct : B. 2
89. To which of the following class does a CNF-satisfiability problem belong?
Correct : C. np complete
90. How many steps are required to prove that a decision problem is NP complete?
Correct : B. 2
91. Which of the following problems is not NP complete?
Correct : D. halting problem
92. The choice of polynomial class has led to the development of an extensive theory called
Correct : A. computational complexity
93. Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
Correct : A. branch and bound
94. The problem of finding a path in a graph that visits every vertex exactly once is called?
Correct : A. hamiltonian path problem
95. Hamiltonian path problem is
Correct : D. np complete problem
96. There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem.
Correct : B. false
97. Which of the following problems is similar to that of a Hamiltonian path problem?
Correct : C. travelling salesman problem
98. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
Correct : A. martello
99. In what time can the Hamiltonian path problem can be solved using dynamic programming?
Correct : D. o(n2 2n)
100. In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.