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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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