In many situations we are faced with a problem of pairing elements of two sets. The traditional example is boys and girls for a dance, but you can easily think of more serious applications.

**Maximum Matching in Bipartite
Graphs**

In many situations we are
faced with a problem of pairing elements of two sets. The traditional example
is boys and girls for a dance, but you can easily think of more serious
applications. It is convenient to represent elements of two given sets by vertices
of a graph, with edges between vertices that can be paired. A ** matching
**in a graph is a subset of its edges with the property that no two edges

We limit our discussion in
this section to the simpler case of bipartite graphs. In a ** bipartite graph**, all the
vertices can be partitioned into two disjoint sets

the vertex set of a given
bipartite graph has been already partitioned into sets ** V** and

Let us apply the
iterative-improvement technique to the maximum-cardinality-matching problem.
Let ** M** be a matching in a bipartite
graph

Another obvious observation
is that we can immediately increase a current matching by adding an edge
between two free vertices. For example, adding ** (**1

In general, we increase the
size of a current matching ** M** by constructing a simple
path from a free vertex in

matching *M***_{d}** is not only a maximum matching but also

Before we discuss an
algorithm for finding an augmenting path, let us settle the issue of what
nonexistence of such a path means. According to the theorem discovered by the
French mathematician Claude Berge, it means the current matching is maximal.

**THEOREM
**A
matching** M **is a maximum matching if and
only if there exists no

**PROOF
**If an
augmenting path with respect to a matching** M **exists, then the size

**
**⊕

* *

* *^{∗} − ** M**. Since |

*
*^{∗} − ** M**
is the same for any even-length cycle of alternating edges in

* *

^{∗} − ** M.** Hence, this is an augmenting path for the
matching

Our discussion of augmenting
paths leads to the following general method for constructing a maximum matching
in a bipartite graph. Start with some initial matching (e.g., the empty set).
Find an augmenting path and augment the current matching along this path. When
no augmenting path can be found, terminate the algorithm and return the last
matching, which is maximum.

We now give a specific
algorithm implementing this general template. We will search for an augmenting
path for a matching ** M** by a BFS-like traversal of
the graph that starts simultaneously at all the free vertices in one of the
sets

**Case 1 **(the queue’s front vertex** ***w*** **is in** ***V )*** **If** ***u*** **is a free vertex adjacent to** **** w**, it is used as the other endpoint of an
augmenting path; so the labeling stops

**Case 2 **(the front vertex** ***w*** **is in** ***U )*** **In this case,** ***w*** **must be matched and we** **label its mate in ** V** with

Here is pseudocode of the
algorithm in its entirety.

**ALGORITHM** *MaximumBipartiteMatching(G)*

//Finds a maximum matching in
a bipartite graph by a BFS-like traversal //Input: A bipartite graph ** G** =

//Output: A
maximum-cardinality matching ** M** in the input graph
initialize set

queue Q with all the free
vertices in V (in any order)

while not Empty(Q) do

w ← Front(Q); Dequeue(Q)

if w ∈ V

for every vertex u adjacent
to w do

if u is free

//augment

M ← M ∪ (w, u)

v ← w

while v is labeled do M ← M − (v, u)

u ← vertex indicated by v’s
label;

v ← vertex indicated by u’s
label; M ← M ∪ (v, u)

remove all vertex labels

reinitialize Q with all free
vertices in V

break //exit the for loop

else //u is matched

if (w, u) ∈ M and u
is unlabeled

label u with w

Enqueue(Q, u)

else //w ∈ U (and
matched)

label the mate v of w with w

Enqueue(Q, v)

return M //current matching is maximum

An application of this
algorithm to the matching in Figure 10.9a is shown in Figure 10.10. Note that
the algorithm finds a maximum matching that differs from the one in Figure
10.9d.

How efficient is the
maximum-matching algorithm? Each iteration except the last one matches two
previously free vertices—one from each of the sets ** V** and

an array.) Hence, the time
efficiency of the algorithm is in ** O(n(n** +

and Karp [Hop73] showed how the efficiency can
be improved to ** O(
n(n** +

We were concerned in this
section with matching the largest possible number of vertex pairs in a
bipartite graph. Some applications may require taking into ac-count the quality
or cost of matching different pairs. For example, workers may execute jobs with
different efficiencies, or girls may have different preferences for their
potential dance partners. It is natural to model such situations by bipartite
graphs with weights assigned to their edges. This leads to the problem of
maxi-mizing the sum of the weights on edges connecting matched pairs of
vertices. This problem is called ** maximum-weight matching**. We
encountered it under a differ-ent name—the assignment problem—in Section 3.4.
There are several sophisti-cated algorithms for this problem, which are much
more efficient than exhaustive search (see, e.g., [Pap82], [Gal86], [Ahu93]).
We have to leave them outside of our discussion, however, because of their
complexity, especially for general graphs.

**Exercises 10.3**

For each matching shown below
in bold, find an augmentation or explain why no augmentation exists.

**2. **Apply the maximum-matching algorithm to the following bipartite
graph:

**
****a. **What is the largest and what
is the smallest possible cardinality of a matching in a bipartite graph ** G** =

**
**What is the largest and what is the smallest number of distinct
solutions the maximum-cardinality-matching problem can have for a bipartite
graph ** G **=

**a. Hall’s Marriage Theorem
**asserts
that a bipartite graph

**
**You have to devise an algorithm that returns yes if there is a
matching in a bipartite graph ** G** =

**
**Suppose there are five committees ** A, B, C, D,** and

**
**Show how the maximum-cardinality-matching problem for a bipartite
graph can be reduced to the maximum-flow problem discussed in Section 10.2.

**
**Consider the following greedy algorithm for finding a maximum
matching in a bipartite graph ** G** =

**
**Design a linear-time algorithm for finding a maximum matching in a
tree.

Implement the
maximum-matching algorithm of this section in the language of your choice.
Experiment with its performance on bipartite graphs with ** n** vertices in each of the vertex sets and
randomly generated edges (in both dense and sparse modes) to compare the
observed running time with the algorithm’s theoretical efficiency.

**
***Domino puzzle *A domino is a 2* *×* *1 tile that can be oriented
either hori-zontally or vertically. A tiling of a given board composed of 1 × 1 squares is covering it with dominoes exactly
and without overlap. Is it possible to tile with dominoes an 8 × 8 board without two unit squares at its
diagonally opposite corners?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Iterative Improvement : Maximum Matching in Bipartite Graphs |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.