This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Maximum Bipartite Matching”.
1. _____________ is a matching with the largest number of edges.
a) Maximum bipartite matching
b) Non-bipartite matching
c) Stable marriage
d) Simplex
View Answer
Explanation: Maximum bipartite matching matches two elements with a property that no two edges share a vertex.
2. Maximum matching is also called as maximum cardinality matching.
a) True
b) False
View Answer
Explanation: Maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges.
3. How many colours are used in a bipartite graph?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: A bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours.
4. 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
View Answer
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.
5. A matching that matches all the vertices of a graph is called?
a) Perfect matching
b) Cardinality matching
c) Good matching
d) Simplex matching
View Answer
Explanation: A matching that matches all the vertices of a graph is called perfect matching.
6. What is the length of an augmenting path?
a) Even
b) Odd
c) Depends on graph
d) 1
View Answer
Explanation: The length of an augmenting path in a bipartite graph is always said to be always odd.
7. 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
View Answer
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.
8. A matching M is maximal if and only if there exists no augmenting path with respect to M.
a) True
b) False
View Answer
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.
9. 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
View Answer
Explanation: Pairing boys and girls for a dance is a traditional example for matching. Proposal of marriage is an application of stable marriage problem.
10. 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
View Answer
Explanation: The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).
11. 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
View Answer
Explanation: The problem is called as maximum weight matching which is similar to a bipartite matching. It is also called as assignment problem.
12. What is the total number of iterations used in a maximum- matching algorithm?
a) [n/2]
b) [n/3]
c) [n/2]+n
d) [n/2]+1
View Answer
Explanation: The total number of iterations cannot exceed [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.
13. What is the efficiency of algorithm designed by Hopcroft and Karp?
a) O(n+m)
b) O(n(n+m)
c) O(√n(n+m))
d) O(n+2)
View Answer
Explanation: The efficiency of algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).
14. Who was the first person to solve the maximum matching problem?
a) Jack Edmonds
b) Hopcroft
c) Karp
d) Claude Berge
View Answer
Explanation: Jack Edmonds was the first person to solve the maximum matching problem in 1965.
15. 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
View Answer
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.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Check Computer Science Books
- Check Design and Analysis of Algorithms Books
- Check Programming Books
- Practice Programming MCQs
- Practice Data Structure MCQ
