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.