McqMate
| 301. |
Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them? |
| A. | number of vertices in u = number of vertices in v |
| B. | sum of degrees of vertices in u = sum of degrees of vertices in v |
| C. | number of vertices in u > number of vertices in v |
| D. | nothing can be said |
| Answer» B. sum of degrees of vertices in u = sum of degrees of vertices in v | |
| Explanation: we can prove this by induction. by adding one edge, the degree of vertices in u is equal to 1 as well as in v. let us assume that this is true for n-1 edges and add one more edge. since the given edge adds exactly once to both u and v we can tell that this statement is true for all n vertices. | |
| 302. |
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? |
| A. | number of vertices in u=number of vertices in v |
| B. | number of vertices in u not equal to number of vertices in v |
| C. | number of vertices in u always greater than the number of vertices in v |
| D. | nothing can be said |
| Answer» A. number of vertices in u=number of vertices in v | |
| Explanation: we know that in a bipartite graph sum of degrees of vertices in u=sum of degrees of vertices in v. given that the graph is a k-regular bipartite graph, we have k* (number of vertices in u)=k*(number of vertices in v). | |
| 303. |
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? |
| A. | n |
| B. | n/2 |
| C. | n/4 |
| D. | data insufficient |
| Answer» B. n/2 | |
| Explanation: we can prove this by calculus. let x be the total number of vertices on set x. therefore set y will have n-x. we have to maximize x*(n-x). this is true when x=n/2. | |
| 304. |
When is a graph said to be bipartite? |
| 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 |
| B. | if the graph is connected and it has odd number of vertices |
| C. | if the graph is disconnected |
| D. | if the graph has at least n/2 vertices whose degree is greater than n/2 |
| Answer» 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 | |
| Explanation: a graph is said to be bipartite if it can be divided into two independent sets a and b such that each edge connects a vertex from a to b. | |
| 305. |
Are trees bipartite? |
| A. | yes |
| B. | no |
| C. | yes if it has even number of vertices |
| D. | no if it has odd number of vertices |
| Answer» A. yes | |
| Explanation: condition needed is that there should not be an odd cycle. but in a tree there are no cycles at all. hence it is bipartite. | |
| 306. |
A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite) |
| A. | 100 |
| B. | 140 |
| C. | 80 |
| D. | 20 |
| Answer» A. 100 | |
| Explanation: let the given bipartition x have x vertices, then y will have 20-x vertices. we need to maximize x*(20-x). this will be maxed when x=10. | |
| 307. |
Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite? |
| A. | yes |
| B. | no |
| Answer» A. yes | |
| Explanation: it is required that the graph is connected also. if it is not then it cannot be called a bipartite graph. | |
| 308. |
Can there exist a graph which is both eulerian and is bipartite? |
| A. | yes |
| B. | no |
| C. | yes if it has even number of edges |
| D. | nothing can be said |
| Answer» A. yes | |
| Explanation: if a graph is such that there exists a path which visits every edge atleast once, then it is said to be eulerian. taking an example of a square, the given question evaluates to yes. | |
| 309. |
A graph is found to be 2 colorable. What can be said about that graph? |
| A. | the given graph is eulerian |
| B. | the given graph is bipartite |
| C. | the given graph is hamiltonian |
| D. | the given graph is planar |
| Answer» B. the given graph is bipartite | |
| Explanation: a graph is said to be colorable if two vertices connected by an edge are never of the same color. 2 colorable mean that this can be achieved with just 2 colors. | |
| 310. |
Which type of graph has no odd cycle in it? |
| A. | bipartite |
| B. | histogram |
| C. | cartesian |
| D. | pie |
| Answer» A. bipartite | |
| Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. odd length cycle means a cycle with the odd number of vertices in it. | |
| 311. |
What type of graph has chromatic number less than or equal to 2? |
| A. | histogram |
| B. | bipartite |
| C. | cartesian |
| D. | tree |
| Answer» B. bipartite | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is chromatic number. | |
| 312. |
Which of the following is the correct type of spectrum of the bipartite graph? |
| A. | symmetric |
| B. | anti – symmetric |
| C. | circular |
| D. | exponential |
| Answer» A. symmetric | |
| Explanation: the spectrum of the bipartite graph is symmetric in nature. the spectrum is the property of graph that are related to polynomial, eigen values, eigen vectors of the matrix related to graph. | |
| 313. |
Which of the following is not a property of the bipartite graph? |
| A. | no odd cycle |
| B. | symmetric spectrum |
| C. | chromatic number is less than or equal to 2 |
| D. | asymmetric spectrum |
| Answer» D. asymmetric spectrum | |
| Explanation: a graph is known to be bipartite if it has odd length cycle number. it also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2. | |
| 314. |
Which one of the following is the chromatic number of bipartite graph? |
| A. | 1 |
| B. | 4 |
| C. | 3 |
| D. | 5 |
| Answer» A. 1 | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. | |
| 315. |
Which graph has a size of minimum vertex cover equal to maximum matching? |
| A. | cartesian |
| B. | tree |
| C. | heap |
| D. | bipartite |
| Answer» D. bipartite | |
| Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. | |
| 316. |
Which theorem gives the relation between the minimum vertex cover and maximum matching? |
| A. | konig’s theorem |
| B. | kirchhoff’s theorem |
| C. | kuratowski’s theorem |
| D. | kelmans theorem |
| Answer» A. konig’s theorem | |
| Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. | |
| 317. |
Which of the following is not a property of perfect graph? |
| A. | compliment of line graph of bipartite graph |
| B. | compliment of bipartite graph |
| C. | line graph of bipartite graph |
| D. | line graph |
| Answer» D. line graph | |
| Explanation: tthe compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is known as a perfect graph in graph theory. normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph. | |
| 318. |
Which of the following has maximum clique size 2? |
| A. | perfect graph |
| B. | tree |
| C. | histogram |
| D. | cartesian |
| Answer» A. perfect graph | |
| Explanation: the perfect bipartite graph has clique size 2. also, the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. | |
| 319. |
What is the chromatic number of compliment of line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| Explanation: the perfect bipartite graph has chromatic number 2. so the compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph has chromatic number 2. | |
| 320. |
What is the clique size of the line graph of bipartite graph? |
| A. | 0 |
| B. | 1 |
| C. | 2 |
| D. | 3 |
| Answer» C. 2 | |
| Explanation: the perfect bipartite graph has clique size 2. so the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. | |
| 321. |
It is possible to have a negative chromatic number of bipartite graph. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. but the chromatic number cannot be negative. | |
| 322. |
Every Perfect graph has forbidden graph characterization. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: berge theorem proves the forbidden graph characterization of every perfect graphs. because of that reason every bipartite graph is perfect graph. | |
| 323. |
Which structure can be modelled by using Bipartite graph? |
| A. | hypergraph |
| B. | perfect graph |
| C. | hetero graph |
| D. | directed graph |
| Answer» A. hypergraph | |
| Explanation: a combinatorial structure such as hypergraph can be made using the bipartite graphs. a hypergraph in graph | |
| 324. |
Which type of graph has all the vertex of the first set connected to all the vertex of the second set? |
| A. | bipartite |
| B. | complete bipartite |
| C. | cartesian |
| D. | pie |
| Answer» B. complete bipartite | |
| Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. the complete bipartite graph has all the vertex of first set connected to all the vertex of second set. | |
| 325. |
Which graph is also known as biclique? |
| A. | histogram |
| B. | complete bipartite |
| C. | cartesian |
| D. | tree |
| Answer» B. complete bipartite | |
| Explanation: a graph is known as complete bipartite graph if and only if it has all the vertex of first set connected to all the vertex of second set. complete bipartite graph is also known as biclique. | |
| 326. |
Which term defines all the complete bipartite graph that are trees? |
| A. | symmetric |
| B. | anti – symmetric |
| C. | circular |
| D. | stars |
| Answer» D. stars | |
| Explanation: star is a complete bipartite graph with one internal node and k leaves. therefore, all complete bipartite graph which is trees are known as stars in graph theory. | |
| 327. |
How many edges does a n vertex triangle free graph contains? |
| A. | n2 |
| B. | n2 + 2 |
| C. | n2 / 4 |
| D. | n3 |
| Answer» C. n2 / 4 | |
| Explanation: a n vertex triangle free graph contains a total of n2 / 4 number of edges. this is stated by mantel’s theorem which is a special case in turan’s theorem for r=2. | |
| 328. |
Which graph is used to define the claw free graph? |
| A. | bipartite graph |
| B. | claw graph |
| C. | star graph |
| D. | cartesian graph |
| Answer» B. claw graph | |
| Explanation: star is a complete bipartite graph with one internal node and k leaves. star with three edges is called a claw. hence this graph is used to define claw free graph. | |
| 329. |
What is testing of a complete bipartite subgraph in a bipartite graph problem called? |
| A. | p problem |
| B. | p-complete problem |
| C. | np problem |
| D. | np-complete problem |
| Answer» D. np-complete problem | |
| Explanation: np stands for nondeterministic polynomial time. in a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an np-complete problem. | |
| 330. |
Which graph cannot contain K3, 3 as a minor of graph? |
| A. | planar graph |
| B. | outer planar graph |
| C. | non planar graph |
| D. | inner planar graph |
| Answer» A. planar graph | |
| Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off | |
| 331. |
Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph? |
| A. | (nm)1/2 |
| B. | (-nm)1/2 |
| C. | 0 |
| D. | nm |
| Answer» D. nm | |
| Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. therefore, the eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0. | |
| 332. |
Which complete graph is not present in minor of Outer Planar Graph? |
| A. | k3, 3 |
| B. | k3, 1 |
| C. | k3, 2 |
| D. | k1, 1 |
| Answer» C. k3, 2 | |
| Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. hence outer planar graph cannot contain k3, 2 as a minor graph. | |
| 333. |
Is every complete bipartite graph a Moore Graph. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: in graph theory, moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a moore graph. | |
| 334. |
What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value? |
| A. | 1 |
| B. | n + m – 2 |
| C. | 0 |
| D. | 2 |
| Answer» B. n + m – 2 | |
| Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. the multiplicity of the adjacency matrix off complete bipartite graph with eigen value 0 is n + m – 2. | |
| 335. |
Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph? |
| A. | n + m |
| B. | n |
| C. | 0 |
| D. | n*m |
| Answer» D. n*m | |
| Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. therefore, the eigen values for the complete bipartite graph is found to be n + m, n, m, 0. | |
| 336. |
What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value? |
| A. | 1 |
| B. | m-1 |
| C. | n-1 |
| D. | 0 |
| Answer» B. m-1 | |
| Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. the multiplicity of the laplacian matrix of complete bipartite graph with eigen value n is m-1. | |
| 337. |
Is it true that every complete bipartite graph is a modular graph. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: yes, the modular graph in graph theory is defined as an undirected | |
| 338. |
How many spanning trees does a complete bipartite graph contain? |
| A. | nm |
| B. | mn-1 * nn-1 |
| C. | 1 |
| D. | 0 |
| Answer» B. mn-1 * nn-1 | |
| Explanation: spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. so, there are a total of mn-1 | |
| 339. |
What does Maximum flow problem involve? |
| A. | finding a flow between source and sink that is maximum |
| B. | finding a flow between source and sink that is minimum |
| C. | finding the shortest path between source and sink |
| D. | computing a minimum spanning tree |
| Answer» A. finding a flow between source and sink that is maximum | |
| Explanation: the maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum and not minimum. | |
| 340. |
A network can have only one source and one sink. |
| A. | false |
| B. | true |
| Answer» B. true | |
| Explanation: a network can have only one source and one sink inorder to find the feasible flow in a weighted connected graph. | |
| 341. |
What is the source? |
| A. | vertex with no incoming edges |
| B. | vertex with no leaving edges |
| C. | centre vertex |
| D. | vertex with the least weight |
| Answer» A. vertex with no incoming edges | |
| Explanation: vertex with no incoming edges is called as a source. vertex with no leaving edges is called as a sink. | |
| 342. |
Which algorithm is used to solve a maximum flow problem? |
| A. | prim’s algorithm |
| B. | kruskal’s algorithm |
| C. | dijkstra’s algorithm |
| D. | ford-fulkerson algorithm |
| Answer» D. ford-fulkerson algorithm | |
| Explanation: ford-fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network. | |
| 343. |
Does Ford- Fulkerson algorithm use the idea of? |
| A. | naïve greedy algorithm approach |
| B. | residual graphs |
| C. | minimum cut |
| D. | minimum spanning tree |
| Answer» B. residual graphs | |
| Explanation: ford-fulkerson algorithm uses the idea of residual graphs which is an extension of naïve greedy approach allowing undo operations. | |
| 344. |
The first step in the naïve greedy algorithm is? |
| A. | analysing the zero flow |
| B. | calculating the maximum flow using trial and error |
| C. | adding flows with higher values |
| D. | reversing flow if required |
| Answer» A. analysing the zero flow | |
| Explanation: the first step in the naïve greedy algorithm is to start with the zero flow followed by adding edges with higher values. | |
| 345. |
Under what condition can a vertex combine and distribute flow in any manner? |
| A. | it may violate edge capacities |
| B. | it should maintain flow conservation |
| C. | the vertex should be a source vertex |
| D. | the vertex should be a sink vertex |
| Answer» B. it should maintain flow conservation | |
| Explanation: a vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation. | |
| 346. |
Find the maximum flow from the following graph. |
| A. | 22 |
| B. | 17 |
| C. | 15 |
| D. | 20 |
| Answer» C. 15 | |
| Explanation: initially, zero flow is computed. then, computing flow= 7+1+5+2=15. hence, maximum flow=15. | |
| 347. |
A simple acyclic path between source and sink which pass through only positive weighted edges is called? |
| A. | augmenting path |
| B. | critical path |
| C. | residual path |
| D. | maximum path |
| Answer» A. augmenting path | |
| Explanation: augmenting path between source and sink is a simple path without cycles. path consisting of zero slack edges is called critical path. | |
| 348. |
Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: dinic’s algorithm includes construction of level graphs and reslidual graphs and finding of augmenting paths along with blocking flow and is faster than the | |
| 349. |
Who is the formulator of Maximum flow problem? |
| A. | lester r. ford and delbert r. fulkerson |
| B. | t.e. harris and f.s. ross |
| C. | y.a. dinitz |
| D. | kruskal |
| Answer» B. t.e. harris and f.s. ross | |
| Explanation: the first ever people to | |
| 350. |
How many constraints does flow have? |
| A. | one |
| B. | three |
| C. | two |
| D. | four |
| Answer» C. two | |
| Explanation: a flow is a mapping which follows two constraints- conservation of flows and capacity constraints. | |
| 351. |
Stable marriage problem is an example of? |
| A. | branch and bound algorithm |
| B. | backtracking algorithm |
| C. | greedy algorithm |
| D. | divide and conquer algorithm |
| Answer» B. backtracking algorithm | |
| Explanation: stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution. | |
| 352. |
Which of the following algorithms does Stable marriage problem uses? |
| A. | gale-shapley algorithm |
| B. | dijkstra’s algorithm |
| C. | ford-fulkerson algorithm |
| D. | prim’s algorithm |
| Answer» A. gale-shapley algorithm | |
| Explanation: stable marriage problem uses gale-shapley algorithm. maximum flow problem uses ford-fulkerson algorithm. | |
| 353. |
An optimal solution satisfying men’s preferences is said to be? |
| A. | man optimal |
| B. | woman optimal |
| C. | pair optimal |
| D. | best optimal |
| Answer» A. man optimal | |
| Explanation: an optimal solution satisfying men’s preferences are said to be man optimal. an optimal solution satisfying woman’s preferences are said to be woman optimal. | |
| 354. |
When a free man proposes to an available woman, which of the following happens? |
| A. | she will think and decide |
| B. | she will reject |
| C. | she will replace her current mate |
| D. | she will accept |
| Answer» D. she will accept | |
| Explanation: when a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list. | |
| 355. |
If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: if there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable. | |
| 356. |
How many 2*2 matrices are used in this problem? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: two 2*2 matrices are used. one for men representing corresponding woman and ranking and the other for women. | |
| 357. |
What happens when a free man approaches a married woman? |
| A. | she simply rejects him |
| B. | she simply replaces her mate with him |
| C. | she goes through her preference list and accordingly, she replaces her current mate with him |
| D. | she accepts his proposal |
| Answer» C. she goes through her preference list and accordingly, she replaces her current mate with him | |
| Explanation: if the preference of the man is greater, she replaces her current mate with him, leaving her current mate free. | |
| 358. |
In case of stability, how many symmetric possibilities of trouble can occur? |
| A. | 1 |
| B. | 2 |
| C. | 4 |
| D. | 3 |
| Answer» B. 2 | |
| Explanation: possibilities- there might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well. | |
| 359. |
Which of the following happens? |
| A. | w2 replaces m1 with m2 |
| B. | w2 rejects m2 |
| C. | w2 accepts both m1 and m2 |
| D. | w2 rejects both m1 and m2 |
| Answer» A. w2 replaces m1 with m2 | |
| Explanation: w2 is married to m1. but the preference of w2 has m2 before m1. hence, w2 replaces m1 with m2. | |
| 360. |
Who formulated a straight forward backtracking scheme for stable marriage problem? |
| A. | mcvitie and wilson |
| B. | gale |
| C. | ford and fulkerson |
| D. | dinitz |
| Answer» A. mcvitie and wilson | |
| Explanation: mcvitie and wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. ford and fulkerson formulated maximum flow problem. | |
| 361. |
Can stable marriage cannot be solved using branch and bound algorithm. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor. | |
| 362. |
What is the prime task of the stable marriage problem? |
| A. | to provide man optimal solution |
| B. | to provide woman optimal solution |
| C. | to determine stability of marriage |
| D. | to use backtracking approach |
| Answer» C. to determine stability of marriage | |
| Explanation: the prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others. | |
| 363. |
Which of the following problems is related to stable marriage problem? |
| A. | choice of school by students |
| B. | n-queen problem |
| C. | arranging data in a database |
| D. | knapsack problem |
| Answer» A. choice of school by students | |
| Explanation: choice of school by students is the most related example in the given set of options since both school and students will have a preference list. | |
| 364. |
What is the efficiency of Gale-Shapley algorithm used in stable marriage problem? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(log n) |
| Answer» C. o(n2) | |
| Explanation: the time efficiency of gale- shapley algorithm is mathematically found to be o(n2) where n denotes stable marriage problem. | |
| 365. |
is a matching with the largest number of edges. |
| A. | maximum bipartite matching |
| B. | non-bipartite matching |
| C. | stable marriage |
| D. | simplex |
| Answer» A. maximum bipartite matching | |
| Explanation: maximum bipartite matching matches two elements with a property that no two edges share a vertex. | |
| 366. |
Maximum matching is also called as maximum cardinality matching. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges. | |
| 367. |
How many colours are used in a bipartite graph? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: a bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours. | |
| 368. |
What is the simplest method to prove that a graph is bipartite? |
| A. | it has a cycle of an odd length |
| B. | it does not have cycles |
| C. | it does not have a cycle of an odd length |
| D. | both odd and even cycles are formed |
| Answer» C. it does not have a cycle of an odd length | |
| Explanation: it is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length. | |
| 369. |
A matching that matches all the vertices of a graph is called? |
| A. | perfect matching |
| B. | cardinality matching |
| C. | good matching |
| D. | simplex matching |
| Answer» A. perfect matching | |
| Explanation: a matching that matches all the vertices of a graph is called perfect matching. | |
| 370. |
What is the length of an augmenting path? |
| A. | even |
| B. | odd |
| C. | depends on graph |
| D. | 1 |
| Answer» B. odd | |
| Explanation: the length of an augmenting path in a bipartite graph is always said to be always odd. | |
| 371. |
In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called? |
| A. | bipartite matching |
| B. | cardinality matching |
| C. | augmenting |
| D. | weight matching |
| Answer» C. augmenting | |
| Explanation: a simple path from a free vertex in v to a free vertex in u whose edges alternate between edges not in m and edges in m is called a augmenting path. | |
| 372. |
A matching M is maximal if and only if there exists no augmenting path with respect to M. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: according to the theorem discovered by the french mathematician claude berge, it means that the current matching is maximal if there is no augmenting path. | |
| 373. |
Which one of the following is an application for matching? |
| A. | proposal of marriage |
| B. | pairing boys and girls for a dance |
| C. | arranging elements in a set |
| D. | finding the shortest traversal path |
| Answer» B. pairing boys and girls for a dance | |
| Explanation: pairing boys and girls for a dance is a traditional example for matching. proposal of marriage is an application of stable marriage problem. | |
| 374. |
Which is the correct technique for finding a maximum matching in a graph? |
| A. | dfs traversal |
| B. | bfs traversal |
| C. | shortest path traversal |
| D. | heap order traversal |
| Answer» B. bfs traversal | |
| Explanation: the correct technique for finding a maximum matching in a bipartite graph is by using a breadth first search(bfs). | |
| 375. |
The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is? |
| A. | maximum- mass matching |
| B. | maximum bipartite matching |
| C. | maximum weight matching |
| D. | maximum node matching |
| Answer» C. maximum weight matching | |
| Explanation: the problem is called as maximum weight matching which is similar to a bipartite matching. it is also called as assignment problem. | |
| 376. |
Who was the first person to solve the maximum matching problem? |
| A. | jack edmonds |
| B. | hopcroft |
| C. | karp |
| D. | claude berge |
| Answer» A. jack edmonds | |
| Explanation: jack edmonds was the first person to solve the maximum matching problem in 1965. | |
| 377. |
From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm? |
| A. | 5 |
| B. | 4 |
| C. | 3 |
| D. | 2 |
| Answer» A. 5 | |
| Explanation: one of the solutions of the matching problem is given by a-w,b-v,c-x,d- y,e-z. hence the answer is 5. | |
| 378. |
The worst-case efficiency of solving a problem in polynomial time is? |
| A. | o(p(n)) |
| B. | o(p( n log n)) |
| C. | o(p(n2)) |
| D. | o(p(m log n)) |
| Answer» A. o(p(n)) | |
| Explanation: the worst-case efficiency of solving an problem in polynomial time is o(p(n)) where p(n) is the polynomial time of input size. | |
| 379. |
Problems that can be solved in polynomial time are known as? |
| A. | intractable |
| B. | tractable |
| C. | decision |
| D. | complete |
| Answer» B. tractable | |
| Explanation: problems that can be solved in polynomial time are known as tractable. | |
| 380. |
The sum and composition of two polynomials are always polynomials. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: one of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials. | |
| 381. |
is the class of decision problems that can be solved by non- deterministic polynomial algorithms? |
| A. | np |
| B. | p |
| C. | hard |
| D. | complete |
| Answer» A. np | |
| Explanation: np problems are called as non- deterministic polynomial problems. they are a class of decision problems that can be solved using np algorithms. | |
| 382. |
Problems that cannot be solved by any algorithm are called? |
| A. | tractable problems |
| B. | intractable problems |
| C. | undecidable problems |
| D. | decidable problems |
| Answer» C. undecidable problems | |
| Explanation: problems cannot be solved by any algorithm are called undecidable problems. problems that can be solved in polynomial time are called tractable problems. | |
| 383. |
The Euler’s circuit problem can be solved in? |
| A. | o(n) |
| B. | o( n log n) |
| C. | o(log n) |
| D. | o(n2) |
| Answer» D. o(n2) | |
| Explanation: mathematically, the run time of euler’s circuit problem is determined to be o(n2). | |
| 384. |
To which class does the Euler’s circuit problem belong? |
| A. | p class |
| B. | np class |
| C. | partition class |
| D. | complete class |
| Answer» A. p class | |
| Explanation: euler’s circuit problem can be solved in polynomial time. it can be solved in o(n2). | |
| 385. |
Halting problem is an example for? |
| A. | decidable problem |
| B. | undecidable problem |
| C. | complete problem |
| D. | trackable problem |
| Answer» B. undecidable problem | |
| Explanation: halting problem by alan turing cannot be solved by any algorithm. hence, it is undecidable. | |
| 386. |
How many stages of procedure does a non- deterministic algorithm consist of? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: a non-deterministic algorithm is a two-stage procedure- guessing stage and verification stage. | |
| 387. |
A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: one of the properties of np class problems states that a non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial. | |
| 388. |
How many conditions have to be met if an NP- complete problem is polynomially reducible? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: a function t that maps all yes instances of decision problems d1 and d2 and t should be computed in polynomial time are the two conditions. | |
| 389. |
To which of the following class does a CNF-satisfiability problem belong? |
| A. | np class |
| B. | p class |
| C. | np complete |
| D. | np hard |
| Answer» C. np complete | |
| Explanation: the cnf satisfiability problem belongs to np complete class. it deals with boolean expressions. | |
| 390. |
How many steps are required to prove that a decision problem is NP complete? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| Explanation: first, the problem should be np. next, it should be proved that every problem in np is reducible to the problem in question in polynomial time. | |
| 391. |
Which of the following problems is not NP complete? |
| A. | hamiltonian circuit |
| B. | bin packing |
| C. | partition problem |
| D. | halting problem |
| Answer» D. halting problem | |
| Explanation: hamiltonian circuit, bin packing, partition problems are np complete problems. halting problem is an undecidable problem. | |
| 392. |
The choice of polynomial class has led to the development of an extensive theory called |
| A. | computational complexity |
| B. | time complexity |
| C. | problem complexity |
| D. | decision complexity |
| Answer» A. computational complexity | |
| Explanation: an extensive theory called computational complexity seeks to classify problems according to their inherent difficulty. | |
| 393. |
Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently? |
| A. | branch and bound |
| B. | iterative improvement |
| C. | divide and conquer |
| D. | greedy algorithm |
| Answer» A. branch and bound | |
| Explanation: the hamiltonian path problem can be solved efficiently using branch and bound approach. it can also be solved using a backtracking approach. | |
| 394. |
The problem of finding a path in a graph that visits every vertex exactly once is called? |
| A. | hamiltonian path problem |
| B. | hamiltonian cycle problem |
| C. | subset sum problem |
| D. | turnpike reconstruction problem |
| Answer» A. hamiltonian path problem | |
| Explanation: hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas hamiltonian cycle problem is finding a cycle in a graph. | |
| 395. |
Hamiltonian path problem is |
| A. | np problem |
| B. | n class problem |
| C. | p class problem |
| D. | np complete problem |
| Answer» D. np complete problem | |
| Explanation: hamiltonian path problem is found to be np complete. hamiltonian cycle problem is also an np- complete problem. | |
| 396. |
There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem. |
| A. | true |
| B. | false |
| Answer» B. false | |
| Explanation: there is a relationship between hamiltonian path problem and hamiltonian circuit problem. the hamiltonian path in graph g is equal to hamiltonian cycle in graph h under certain conditions. | |
| 397. |
Which of the following problems is similar to that of a Hamiltonian path problem? |
| A. | knapsack problem |
| B. | closest pair problem |
| C. | travelling salesman problem |
| D. | assignment problem |
| Answer» C. travelling salesman problem | |
| Explanation: hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once. | |
| 398. |
Who formulated the first ever algorithm for solving the Hamiltonian path problem? |
| A. | martello |
| B. | monte carlo |
| C. | leonard |
| D. | bellman |
| Answer» A. martello | |
| Explanation: the first ever problem to solve the hamiltonian path was the enumerative algorithm formulated by martello. | |
| 399. |
In what time can the Hamiltonian path problem can be solved using dynamic programming? |
| A. | o(n) |
| B. | o(n log n) |
| C. | o(n2) |
| D. | o(n2 2n) |
| Answer» D. o(n2 2n) | |
| Explanation: using dynamic programming, the time taken to solve the hamiltonian path problem is mathematically found to be o(n2 2n). | |
| 400. |
In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even. |
| A. | true |
| B. | false |
| Answer» A. true | |
| Explanation: according to a handshaking lemma, in graphs, in which all vertices have an odd degree, the number of hamiltonian cycles through any fixed edge is always even. | |
Done Reading?