Engineering Questions with Answers - Multiple Choice Questions
Maximum Bipartite Matching MCQ’s
1 - Question
_____________ is a matching with the largest number of edges.
a) Maximum bipartite matching
b) Non-bipartite matching
c) Stable marriage
d) Simplex
View Answer
Answer: a
Explanation: Maximum bipartite matching matches two elements with a property that no two edges share a vertex.
2 - Question
Maximum matching is also called as maximum cardinality matching.
a) True
b) False
View Answer
Answer: a
Explanation: Maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges.
3 - Question
How many colours are used in a bipartite graph?
a) 1
b) 2
c) 3
d) 4
View Answer
Answer: b
Explanation: A bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours.
4 - Question
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
Answer: c
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 - Question
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
Answer: a
Explanation: A matching that matches all the vertices of a graph is called perfect matching.
6 - Question
What is the length of an augmenting path?
a) Even
b) Odd
c) Depends on graph
d) 1
View Answer
Answer: b
Explanation: The length of an augmenting path in a bipartite graph is always said to be always odd.
7 - Question
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
Answer: c
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 - Question
A matching M is maximal if and only if there exists no augmenting path with respect to M.
a) True
b) False
View Answer
Answer: a
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 - Question
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
Answer: b
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 - Question
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
Answer: b
Explanation: The correct technique for finding a maximum matching in a bipartite graph is by using a Breadth First Search(BFS).
11 - Question
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
Answer: c
Explanation: The problem is called as maximum weight matching which is similar to a bipartite matching. It is also called as assignment problem.
12 - Question
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
Answer: d
Explanation: The total number of iterations cannot exceed [n/2]+1 where n=|V|+|U| denoting the number of vertices in the graph.
13 - Question
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
Answer: c
Explanation: The efficiency of algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).
14 - Question
Who was the first person to solve the maximum matching problem?
a) Jack Edmonds
b) Hopcroft
c) Karp
d) Claude Berge
View Answer
Answer: a
Explanation: Jack Edmonds was the first person to solve the maximum matching problem in 1965.
15 - Question
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
Answer: a
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.